Source-linked AI summary
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson, Huy L. Nguyen
TL;DR
The paper addresses how to construct sparse, data-independent embeddings that preserve low-dimensional subspaces while enabling faster processing of sparse data. It analyzes sparse embeddings using moment-based random matrix techniques and obtains improved dimension–sparsity trade-offs, with applications to numerical linear algebra.
Problem
The problem is to design sparse oblivious subspace embeddings that preserve subspace geometry while avoiding the computation and hash-evaluation costs of earlier constructions.
Method
The paper analyzes sparse embeddings through trace-moment expansions grouped by multigraph structure, and applies the resulting OSEs to numerical linear algebra algorithms.
Results
The paper proves s = 1 embeddings with m = O(d^2/ε^2), and OSNAPs with m = Õ(d/ε^2), s = polylog(d)/ε or m = O(d^{1+γ}/ε^2), s = Oγ(1/ε).
Takeaways & Limitations
The constructions imply faster algorithms for approximate least squares regression, low rank approximation, and leverage-score approximation.
Takeaways & Limitations
The stated algorithmic bounds use the real RAM model and assume numerical routines can attain comparable precision and error guarantees.
Abstract
from arXiv · showhide
An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any linear subspace W in R^n with dim(W) = d it holds that Pr_{B ~ D}(forall x in W ||B x||_2 in (1 +/- eps)||x||_2) > 2/3 We show an OSE exists with m = O(d^2/eps^2) and where every B in the support of D has exactly s=1 non-zero entries per column. This improves previously best known bound in [Clarkson-Woodruff, arXiv:1207.6365]. Our quadratic dependence on d is optimal for any OSE with s=1 [Nelson-Nguyen, 2012]. We also give two OSE's, which we call Oblivious Sparse Norm-Approximating Projections (OSNAPs), that both allow the parameter settings m = Õ(d/eps^2) and s = polylog(d)/eps, or m = O(d^{1+gamma}/eps^2) and s=O(1/eps) for any constant gamma>0. This m is nearly optimal since m >= d is required simply to no non-zero vector of W lands in the kernel of B. These are the first constructions with m=o(d^2) to have s=o(d). In fact, our OSNAPs are nothing more than the sparse Johnson-Lindenstrauss matrices of [Kane-Nelson, SODA 2012]. Our analyses all yield OSE's that are sampled using either O(1)-wise or O(log d)-wise independent hash functions, which provides some efficiency advantages over previous work for turnstile streaming applications. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: i.e. we show that for any U in R^{n x d} with orthonormal columns and random sparse B, all singular values of BU lie in [1-eps, 1+eps] with good probability. Plugging OSNAPs into known algorithms for numerical linear algebra problems such as approximate least squares regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems.
1 Introduction
The paper develops sparse oblivious subspace embeddings that preserve low-dimensional subspaces while reducing computation for sparse data. Its constructions improve embedding dimensions, sparsity, hash-function requirements, and downstream numerical linear algebra runtimes.
- Motivation: OSEs reduce unknown low-dimensional subspaces while preserving all distances, extending the Johnson-Lindenstrauss approach to sparse inputs.They support numerical linear algebra algorithms whose running time can depend on input sparsity.
- Motivation: Naively computing ΠA can cost matrix-multiplication time, motivating structured embeddings that exploit sparse inputs and can be applied in O(nnz(A)) time.Fast structured embeddings previously achieved O(nd log n) time for dense matrices, while sparse inputs call for input-sparsity dependence.
- Implementation: The analyses use lower-wise independence than earlier work, addressing streaming costs associated with identifying nonzeros from an implicit embedding.Earlier constructions required Ω(d)-wise independence, creating additive Ω(d) evaluation time, while the paper targets O(1)- or O(log d)-wise independence.
- Main contribution: m = O(d^2/ε^2) with s = 1 improves the analyzed Clarkson-Woodruff construction and is near-optimal because s = 1 OSEs require m = Ω(d^2).The construction also supports constant-time column recovery with SΠ = O(log(nd)).
- Main contribution: m = Õ(d/ε^2) with s = polylog(d)/ε or m = O(d^{1+γ}/ε^2) with s = Oγ(1/ε) provides two OSNAP parameter regimes.The corresponding column-recovery times are Õ(s) and O((log d)/ε), respectively.
- Analysis: The proof expands tr((S − I)^ℓ), groups monomials by undirected multigraphs, and bounds graph contributions using reductions to even edge multiplicities.This follows the classical moment method and is inspired by Bai-Yin random matrix analysis.
2 Analysis
The analysis reduces OSE guarantees to controlling the singular values of ΠU, then bounds deviations through matrix inequalities, moments, and multigraph structure. It establishes guarantees for both one-sparse sketches and OSNAPs under specified sparsity, dimension, independence, and failure-probability conditions.
- Spectral reduction: All singular values of ΠU must lie in [1 − ε, 1 + ε], equivalently requiring the eigenvalues of S = (ΠU)∗ΠU to lie in [(1 − ε)^2, (1 + ε)^2].The proof writes S = I + (S − I) and uses Weyl’s inequality to control its eigenvalues through the perturbation norm.
- One-sparse construction: Theorem 3 gives the s = 1 guarantee with probability at least 1 − δ when m ≥ δ−1(d^2 + d)/(2ε − ε^2)^2, using 4-wise independent signs and pairwise independent hashing.The construction’s analysis separates diagonal and off-diagonal contributions, with the diagonal terms contributing at most 2d/m to the Frobenius-norm bound.
- Moment method: The proof expands tr((S − I)^ℓ), groups exponentially many monomials by associated undirected multigraphs, and bounds each graph’s contribution before summing over graphs.Random signs eliminate monomials unless every bond in MR(G) has even multiplicity, while OSNAP properties bound the corresponding δ-term expectation by (s/m)^b.
- Graph organization: The dot product multigraph records inner products ⟨u_i, u_j⟩ generated by summing over matrix-index variables, while generalized dot product multigraphs attach matrices to edges.The graph notation tracks bond counts, connected components, and induced multigraphs used in the moment bounds.
- OSNAP guarantees: Theorem 12 achieves s = Θ(1/ε) and m = Ω(d^{1+γ}/ε^2) with probability at least 1 − 1/d^α for arbitrary constants α, γ > 0.The constants in the big-Θ and big-Ω bounds depend on α and γ, and the proof bounds E∥S − I∥^2 before applying Markov’s inequality.
3 Applications
The paper applies its sparse subspace embeddings to leverage-score approximation, least squares regression, and low-rank approximation, yielding improved running-time guarantees. These applications reuse prior algorithms and analyses with the new embedding parameters.
- 3.1 Approximate Leverage Scores: The leverage-score algorithm replaces the Fast Johnson–Lindenstrauss embedding with sparse subspace embeddings while retaining the prior proof outline.The construction first reduces A to r linearly independent columns, then uses an OSNAP and a Johnson–Lindenstrauss matrix.
- 3.2 Least Squares Regression: Least squares regression runs in O(nnz(A) + d^3 log(d/ε)/ε^2) time and succeeds with probability at least 2/3.The reduction applies the s = 1 embedding to the subspace spanned by the columns of A and b, producing a smaller regression problem.
- 3.2 Least Squares Regression: A rank-r least squares algorithm runs in O(nnz(A)((log r)O(1) + log(n/ε)) + r^ω(log r)O(1) + r^2 log(1/ε)) time.This bound uses the embedding of Theorem 9 and the argument from prior work.
- 3.3 Low Rank Approximation: For low-rank approximation, two algorithms succeed with probability at least 3/5 and use the improved sparse-embedding bounds.The first runs in O(nnz(A)) + Õ(nk^2 + nk^ω−1ε−1−ω + k^ωε−2−ω) time; the second has a different input-processing term and the same remaining terms.