STOC Conference 2024 Conference Paper
Optimal Embedding Dimension for Sparse Subspace Embeddings
- Shabarish Chenakkod
- Michal Derezinski
- Xiaoyu Dong
- Mark Rudelson
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 , P ( ∀ x ∈ W (1+є) −1 || x ||≤ || Sx ||≤ (1+є)|| x || )≥ 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 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).