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⊆ Rn, 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.