Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real p; 1 p <1, given a matrix M 2 R n d with n d, with constant probability we can choose a matrix with max(1;n 1 2=p )poly(d) rows and n columns so that simultaneously for all x2 R d ,kMxkp k Mxk1 poly(d)kMxkp: Importantly, M can be computed in the optimalO(nnz(M)) time, where nnz(M) is the number of non-zero entries ofM . This generalizes all previous oblivious subspace embeddings which required p 2 [1; 2] due to their use of p-stable random variables. Using our matrices , we also improve the best known distortion of oblivious subspace embeddings of ‘1 into ‘1 with ~ O(d) target dimension in O(nnz(M)) time from ~ O(d 3 ) to
['David P. Woodruff', 'Qin Zhang']
Subspace Embeddings and $\ell_p$-Regression Using Exponential Random Variables