Fast Fixed Dimension L2-Subspace Embeddings of Arbitrary Accuracy, With Application to L1 and L2 Tasks

September 30, 2019 Abstract We give a fast oblivious null 2-embedding of A R n d to A R r d satisfying (1 ε) nullA x null 2 2 null A x null 2 2 (1 ε)null A xnull 2 2. Our embedding dimension r equals d, a constant independent of the distortion ε . We use as a black-box any null 2-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 null 2 embedding to regression, PCA and statistical leverage scores. We also give applications to null 1: (i) An oblivious null 1 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; (ii) Fast approximation of null 1 Lewis weights using our null 2 embedding to quickly approximate null 2-leverage scores. 1 ...