Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables

David Woodruff, Qin Zhang
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:546-567, 2013.

Abstract

Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real p, 1 ≤p < ∞, given a matrix M ∈\mathbbR^n \times d with n ≫d, with constant probability we can choose a matrix \Pi with \max(1, n^1-2/p) \textpoly(d) rows and n columns so that simultaneously for all x ∈\mathbbR^d, \|Mx\|_p ≤\|\Pi Mx\|_∞ ≤\textpoly(d) \|Mx\|_p. Importantly, \Pi M can be computed in the optimal O(\textnnz(M)) time, where \textnnz(M) is the number of non-zero entries of M. This generalizes all previous oblivious subspace embeddings which required p ∈[1,2] due to their use of p-stable random variables. Using our new matrices \Pi, we also improve the best known distortion of oblivious subspace embeddings of \ell_1 into \ell_1 with \tildeO(d) target dimension in O(\textnnz(M)) time from \tildeO(d^3) to \tildeO(d^2), which can further be improved to \tildeO(d^3/2) \log^1/2 n if d = Ω(\log n), answering a question of Meng and Mahoney (STOC, 2013). We apply our results to \ell_p-regression, obtaining a (1+ε)-approximation in O(\textnnz(M)\log n) + \textpoly(d/ε) time, improving the best known \textpoly(d/ε) factors for every p ∈[1, ∞) ∖{2}. If one is just interested in a \textpoly(d) rather than a (1+ε)-approximation to \ell_p-regression, a corollary of our results is that for all p ∈[1, ∞) we can solve the \ell_p-regression problem without using general convex programming, that is, since our subspace embeds into \ell_∞ it suffices to solve a linear programming problem. Finally, we give the first protocols for the distributed \ell_p-regression problem for every p ≥1 which are nearly optimal in communication and computation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Woodruff13, title = {Subspace Embeddings and $\ell_p$-Regression Using Exponential Random Variables}, author = {Woodruff, David and Zhang, Qin}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {546--567}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Woodruff13.pdf}, url = {https://proceedings.mlr.press/v30/Woodruff13.html}, abstract = {Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real p, 1 ≤p < ∞, given a matrix M ∈\mathbbR^n \times d with n ≫d, with constant probability we can choose a matrix \Pi with \max(1, n^1-2/p) \textpoly(d) rows and n columns so that simultaneously for all x ∈\mathbbR^d, \|Mx\|_p ≤\|\Pi Mx\|_∞ ≤\textpoly(d) \|Mx\|_p. Importantly, \Pi M can be computed in the optimal O(\textnnz(M)) time, where \textnnz(M) is the number of non-zero entries of M. This generalizes all previous oblivious subspace embeddings which required p ∈[1,2] due to their use of p-stable random variables. Using our new matrices \Pi, we also improve the best known distortion of oblivious subspace embeddings of \ell_1 into \ell_1 with \tildeO(d) target dimension in O(\textnnz(M)) time from \tildeO(d^3) to \tildeO(d^2), which can further be improved to \tildeO(d^3/2) \log^1/2 n if d = Ω(\log n), answering a question of Meng and Mahoney (STOC, 2013). We apply our results to \ell_p-regression, obtaining a (1+ε)-approximation in O(\textnnz(M)\log n) + \textpoly(d/ε) time, improving the best known \textpoly(d/ε) factors for every p ∈[1, ∞) ∖{2}. If one is just interested in a \textpoly(d) rather than a (1+ε)-approximation to \ell_p-regression, a corollary of our results is that for all p ∈[1, ∞) we can solve the \ell_p-regression problem without using general convex programming, that is, since our subspace embeds into \ell_∞ it suffices to solve a linear programming problem. Finally, we give the first protocols for the distributed \ell_p-regression problem for every p ≥1 which are nearly optimal in communication and computation.} }
Endnote
%0 Conference Paper %T Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables %A David Woodruff %A Qin Zhang %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Woodruff13 %I PMLR %P 546--567 %U https://proceedings.mlr.press/v30/Woodruff13.html %V 30 %X Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real p, 1 ≤p < ∞, given a matrix M ∈\mathbbR^n \times d with n ≫d, with constant probability we can choose a matrix \Pi with \max(1, n^1-2/p) \textpoly(d) rows and n columns so that simultaneously for all x ∈\mathbbR^d, \|Mx\|_p ≤\|\Pi Mx\|_∞ ≤\textpoly(d) \|Mx\|_p. Importantly, \Pi M can be computed in the optimal O(\textnnz(M)) time, where \textnnz(M) is the number of non-zero entries of M. This generalizes all previous oblivious subspace embeddings which required p ∈[1,2] due to their use of p-stable random variables. Using our new matrices \Pi, we also improve the best known distortion of oblivious subspace embeddings of \ell_1 into \ell_1 with \tildeO(d) target dimension in O(\textnnz(M)) time from \tildeO(d^3) to \tildeO(d^2), which can further be improved to \tildeO(d^3/2) \log^1/2 n if d = Ω(\log n), answering a question of Meng and Mahoney (STOC, 2013). We apply our results to \ell_p-regression, obtaining a (1+ε)-approximation in O(\textnnz(M)\log n) + \textpoly(d/ε) time, improving the best known \textpoly(d/ε) factors for every p ∈[1, ∞) ∖{2}. If one is just interested in a \textpoly(d) rather than a (1+ε)-approximation to \ell_p-regression, a corollary of our results is that for all p ∈[1, ∞) we can solve the \ell_p-regression problem without using general convex programming, that is, since our subspace embeds into \ell_∞ it suffices to solve a linear programming problem. Finally, we give the first protocols for the distributed \ell_p-regression problem for every p ≥1 which are nearly optimal in communication and computation.
RIS
TY - CPAPER TI - Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables AU - David Woodruff AU - Qin Zhang BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Woodruff13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 546 EP - 567 L1 - http://proceedings.mlr.press/v30/Woodruff13.pdf UR - https://proceedings.mlr.press/v30/Woodruff13.html AB - Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real p, 1 ≤p < ∞, given a matrix M ∈\mathbbR^n \times d with n ≫d, with constant probability we can choose a matrix \Pi with \max(1, n^1-2/p) \textpoly(d) rows and n columns so that simultaneously for all x ∈\mathbbR^d, \|Mx\|_p ≤\|\Pi Mx\|_∞ ≤\textpoly(d) \|Mx\|_p. Importantly, \Pi M can be computed in the optimal O(\textnnz(M)) time, where \textnnz(M) is the number of non-zero entries of M. This generalizes all previous oblivious subspace embeddings which required p ∈[1,2] due to their use of p-stable random variables. Using our new matrices \Pi, we also improve the best known distortion of oblivious subspace embeddings of \ell_1 into \ell_1 with \tildeO(d) target dimension in O(\textnnz(M)) time from \tildeO(d^3) to \tildeO(d^2), which can further be improved to \tildeO(d^3/2) \log^1/2 n if d = Ω(\log n), answering a question of Meng and Mahoney (STOC, 2013). We apply our results to \ell_p-regression, obtaining a (1+ε)-approximation in O(\textnnz(M)\log n) + \textpoly(d/ε) time, improving the best known \textpoly(d/ε) factors for every p ∈[1, ∞) ∖{2}. If one is just interested in a \textpoly(d) rather than a (1+ε)-approximation to \ell_p-regression, a corollary of our results is that for all p ∈[1, ∞) we can solve the \ell_p-regression problem without using general convex programming, that is, since our subspace embeds into \ell_∞ it suffices to solve a linear programming problem. Finally, we give the first protocols for the distributed \ell_p-regression problem for every p ≥1 which are nearly optimal in communication and computation. ER -
APA
Woodruff, D. & Zhang, Q.. (2013). Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:546-567 Available from https://proceedings.mlr.press/v30/Woodruff13.html.

Related Material