We give a fast oblivious L2-embedding of $Ain mathbb{R}^{n x d}$ to $Bin mathbb{R}^{r x d}$ satisfying $(1-varepsilon)|A x|_2^2 le |B x|_2^2 <= (1+varepsilon) |Ax|_2^2.$ Our embedding dimension $r$ equals $d$, a constant independent of the distortion $varepsilon$. We use as a black-box any L2-embedding $Pi^T A$ and inherit its runtime and accuracy, effectively decoupling the dimension $r$ from runtime and accuracy, allowing downstream machine learning applications to benefit from both a low dimension and high accuracy (in prior embeddings higher accuracy means higher dimension). We give applications of our L2-embedding to regression, PCA and statistical leverage scores. We also give applications to L1: 1.) An oblivious L1-embedding with dimension $d+O(dln^{1+eta} d)$ and distortion $O((dln d)/lnln d)$, with application to constructing well-conditioned bases; 2.) Fast approximation of L1-Lewis weights using our L2 embedding to quickly approximate L2-leverage scores.
Download