Optimal Embedding Dimension for Sparse Subspace Embeddings

A random m× n matrix S is an oblivious subspace embedding (OSE) with parameters ε>0, δ∈(0,1/3) and d≤ m≤ n, if for any d-dimensional subspace Wsubseteq Rn, Pbig(,forallx∈ W (1+ε)-1|x|≤|Sx|≤ (1+ε)|x|,big)≥ 1-δ. It is known that the embedding dimension of an OSE must satisfy m≥ d, and for any θ > 0, a Gaussian embedding matrix with m≥ (1+θ) d is an OSE with ε = Oθ(1). However, such optimal embedding dimension is not known for other embeddings. Of particular interest are sparse OSEs, having sll m non-zeros per column, with applications to problems such as least squares regression and low-rank approximation. We show that, given any θ > 0, an m× n random matrix S with m≥ (1+θ)d consisting of randomly sparsified ±1/√ s entries and having s= O(log4(d)) non-zeros per column, is an oblivious subspace embedding with ε = Oθ(1). Our result addresses the main open question posed by Nelson and Nguyen (FOCS 2013), who conjectured that sparse OSEs can achieve m=O(d) embedding dimension, and it improves on m=O(dlog(d)) shown by Cohen (SODA 2016). We use this to construct the first oblivious subspace embedding with O(d) embedding dimension that can be applied faster than current matrix multiplication time, and to obtain an optimal single-pass algorithm for least squares regression. We further extend our results to Leverage Score Sparsification (LESS), which is a recently introduced non-oblivious embedding technique. We use LESS to construct the first subspace embedding with low distortion ε=o(1) and optimal embedding dimension m=O(d/ε2) that can be applied in current matrix multiplication time.