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 W ⊆ R n ,

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 s ≪ m non-zeros per column (Clarkson and Woodruff, STOC 2013), 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(log 4 (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(d log(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, addressing a question posed by Cherapanamjeri, Silwal, Woodruff and Zhou (SODA 2023).

Our analysis builds on recent advances in universality theory for random matrices, to overcome the limitations of existing approaches such as those based on matrix concentration inequalities. In the process, we establish new bounds on the extreme singular values for a class of nearly-square random matrices that arise from applying an m×n sparse OSE matrix to an n×d isometric embedding matrix, which may be of independent interest. To maximally leverage these results, we introduce new non-uniformly sparsified embedding constructions which, in particular, reduce the random bit complexity of our OSE to polylog(n).