Fast Fixed Dimension L2-Subspace Embeddings of Arbitrary Accuracy, With Application to L1 and L2 Tasks
This work addresses the efficiency-accuracy trade-off in subspace embeddings for machine learning applications, offering a method that decouples dimension from runtime and accuracy, though it is incremental in building on existing L2-embeddings.
The paper tackles the problem of creating fast L2-subspace embeddings with constant dimension independent of accuracy, achieving an embedding dimension equal to the data dimension d, and applies it to tasks like regression, PCA, and L1 embeddings with specific distortion bounds.
We give a fast oblivious L2-embedding of $A\in \mathbb{R}^{n x d}$ to $B\in \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 $Π^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(d\ln^{1+η} d)$ and distortion $O((d\ln d)/\ln\ln 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.