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.