Source-linked AI summary
Sparser Johnson-Lindenstrauss Transforms
Daniel M. Kane, Jelani Nelson
TL;DR
The paper targets the cost of ℓ2 dimensionality reduction for sparse vectors, where dense or prior sparse embeddings can remain expensive. It introduces graph and block sparse JL constructions, analyzes them using structured hashing and moment bounds, and derives improved sparsity with applications to streaming numerical linear algebra. The work also identifies remaining gaps in the lower bounds for sparsity.
Problem
Existing JL embeddings and prior sparse constructions do not provide sufficiently low application cost for sparse vectors across all parameter settings.
Method
The paper constructs graph and block sparse linear embeddings using structured hashing, random signs, scaling, and moment-based analyses.
Results
The constructions achieve sparsity s = Θ(ε^-1 log(1/δ)) while retaining the JL target dimension, and support faster streaming algorithms for regression and low-rank approximation.
Takeaways & Limitations
Sparse JL distributions can be used to speed up applications of ℓ2 dimensionality reduction and numerical linear algebra while preserving the stated embedding guarantees.
Takeaways & Limitations
A tight lower bound s = Ω(ε^-1 log(1/δ)) remains open when k = O(ε^-2 log(1/δ)) < d/2, leaving an O(log(1/ε)) gap.
Abstract
from arXiv · showhide
We give two different and simple constructions for dimensionality reduction in $\ell_2$ via linear mappings that are sparse: only an $O(\varepsilon)$-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion $1+\varepsilon$ with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas (JCSS 2003) and Dasgupta, Kumar, and Sarlós (STOC 2010). Such distributions can be used to speed up applications where $\ell_2$ dimensionality reduction is used.
1 Introduction
The paper addresses the cost of applying JL embeddings to sparse vectors by introducing sparse linear constructions that preserve ℓ2 geometry with asymptotically optimal target dimension. Its graph and block constructions use structured hashing and moment-based analyses to obtain improved sparsity and support faster numerical linear algebra.
- Motivation: O(ε^-2 log(1/δ)) rows are sufficient for distributional JL, and this target dimension is asymptotically optimal.The JL lemma provides a distribution over k × d matrices with k = Θ(ε^-2 log(1/δ)); the optimality of k is known.
- Motivation: Sparse JL embeddings matter because dense-matrix application costs O(k · ∥x∥0), while prior faster methods still require Ω(d log d) time even for one-sparse vectors.This bottleneck is especially problematic for coordinate-wise streaming updates, where each update changes a vector by a multiple of e_i.
- Motivation: Sparse vectors arise in text, networking, and other applications, motivating embeddings whose running time reflects input sparsity.Examples include bag-of-words documents and communication-count vectors indexed by source–destination IP pairs.
- Contributions: The work also gives simpler-analysis variants with sparsity ˜O(ε^-1 log(1/δ)) and uses sparse JL transforms to obtain faster streaming algorithms for regression and low-rank approximation.It further presents a general reduction for approximate matrix-product sketches without the logarithmic loss incurred by an earlier union-bound reduction.
- Our Approach: The paper introduces two constructions with s = Θ(ε^-1 log(1/δ)) nonzeros per column: a graph construction hashing without replacement and a block construction hashing once per block.Both constructions randomly flip coordinate signs and scale by √s before accumulating contributions in the target vector.
- Our Approach: The analyses use ℓth moments with ℓ = log(1/δ), applying Markov’s bound and, in one approach, Hanson–Wright for a quadratic form in the random signs.The first analysis shows that sufficiently good deterministic codes can replace random hashing, with code quality both necessary and sufficient for controlling collisions.
2 Conventions and Notation
This section fixes notation and conventions for vectors, norms, logarithms, and asymptotic notation used throughout the paper.
- Norms: For A ∈ R^n×n, the Frobenius norm is introduced as ∥A∥F.The supplied passage states the definition but does not include its completed formula.
- Norms: For A ∈ R^n×n, the operator norm is ∥A∥2 = sup∥x∥2=1 ∥Ax∥2.For symmetric A, this norm is also the largest magnitude of an eigenvalue.
- Notation: The paper uses [n] for {1, . . . , n}, takes logarithms to base 2 unless stated otherwise, and treats vectors as columns.It also uses vT for transposes and measures space complexity in bits.
- Assumptions: Because the embeddings are linear, the analysis assumes ∥x∥2 = 1 without loss of generality.The paper also notes that quantities such as 1/δ may be assumed to be powers of 2 or 4.
3 Code-Based Constructions
The code-based constructions use deterministic nonzero locations satisfying a low-collision condition, then analyze sign-induced error with quadratic-form concentration. They achieve the target distortion with sparsity Θ(ε^-1 log(1/δ)) only after an additional parameter restriction, while the code-based route itself requires a larger bound.
- Code-based design: The analysis assumes each pair of columns overlaps in at most O(s^2/k) nonzero rows, a condition supplied by suitable error-correcting codes.For the block construction, this is equivalent to code relative distance 1−O(s/k).
- Analysis: The embedding error is represented as the quadratic form σ^T Tσ, enabling Hanson-Wright and Markov bounds for distortion failure.Here σ contains the random signs and T is a block-diagonal matrix determined by the hashing pattern and input vector.
- Guarantee: Theorem 7 bounds the failure probability by Pσ(|Z| > 2ε−ε^2) < δ under the stated code-based conditions.The proof uses the matrix norm bound ∥T∥2 ≤ 1/s and the moment parameter ℓ=log(1/δ).
- Parameter boundary: Code-based constructions require s = Ω(ε^-1√(log(d/δ) log(1/δ))), which is larger than the desired sparsity in general.The larger requirement arises from ensuring the code condition simultaneously for all column pairs.
- Parameter boundary: The analysis cannot improve sparsity beyond Ω(ε^-1 log(1/δ)) using only the pairwise-overlap condition, because coordinated collisions in one block create error Ω(t/s).Avoiding this bottleneck motivates the random-hashing analysis.
4 Random Hashing Constructions
The random-hashing constructions replace fixed codes with sufficiently independent random hash functions and analyze moments by grouping error monomials according to directed multigraphs. This yields sparsity Θ(ε^-1 log(1/δ)) with k = Θ(ε^-2 log(1/δ)) while preserving the stated distortion guarantee.
- Construction: Randomly chosen, sufficiently independent hash functions achieve sparsity O(ε^-1 log(1/δ)); the graph construction requires almost k-wise independent permutations.This removes the code-construction bottleneck from the preceding section.
- Moment analysis: Negative correlation among nonzero-location indicators lets the moment expansion be dominated term-by-term by the independent-indicator case.This property is used to control products of hashing indicators in the moment bound.
- Moment analysis: The error analysis bounds moments of Z by associating each monomial with a directed multigraph and grouping monomials that share the same graph.The graph representation makes the expectation calculation combinatorial.
- Guarantee: For s ∈ Θ(ε^-1 log(1/δ)) and k ∈ Θ(ε^-2 log(1/δ)), Theorem 13 gives Ph,σ(|Z| > 2ε−ε^2) < δ.The proof uses an even moment ℓ=Θ(log(1/δ)) together with Markov’s inequality.
- Implementation: The graph construction can use fewer random bits through hash functions that select exactly s distinct locations per column and signs from a 2 log(1/δ)-wise independent family.The implementation preserves the fixed-column sparsity while reducing randomness requirements.
5 Tightness of analyses
The analyses are tight up to constant factors: the graph and block constructions require Ω(ε^-1 log(1/δ)) sparsity, while DKS requires Ω(ε^-1 log^2(1/δ)). These lower bounds use explicit hard vectors whose collisions and sign agreements produce distortion with probability exceeding δ.
- DKS construction: Ω(ε^-1 log^2(1/δ)) sparsity is required by the DKS construction to achieve distortion 1 ± ε with success probability 1 − δ.This nearly matches earlier upper bounds and shows that improving DKS requires departing from that construction.
- Hard inputs: For s ≤ 1/(2ε), a vector with t = ⌊1/(sε)⌋ nonzero coordinates can incur distortion at least 1 + 2ε from exactly one collision with agreeing signs.The same hard-vector pattern is used in the lower-bound arguments for the constructions considered.
- Graph construction: Ω(ε^-1 log(1/δ)) sparsity is required for the graph construction to achieve distortion 1 ± ε with success probability 1 − δ.The result applies for k = Cε^-2 log(1/δ) and sufficiently small δ.
- Hard inputs: For larger s ranges, collision patterns involving two or three coordinates can produce error at least 2ε or distortion above 1 + 3ε/2 with probability larger than δ.The arguments combine collision events with sign-agreement events, whose probabilities remain sufficiently large in the stated ranges.
- Block construction: Ω(ε^-1 log(1/δ)) sparsity is likewise required for the block construction to achieve distortion 1 ± ε with success probability 1 − δ.The theorem assumes k = Cε^-2 log(1/δ) and δ below a constant depending on C.
6 Faster numerical linear algebra streaming algorithms
The paper shows that JL-moment distributions yield approximate matrix product sketches, allowing sparse JL constructions to accelerate streaming numerical linear algebra algorithms. It gives improved update and sketch-size guarantees for linear regression and low-rank approximation under several update models.
- Sketching framework: JL moments imply approximate matrix product sketches for arbitrary matrices with matching row dimensions.Theorem 21 generalizes prior matrix-product sketching results and avoids a union bound using Minkowski’s inequality.
- Sketching framework: Sparse JL distributions can replace random Bernoulli matrices in algorithms that maintain SA under matrix updates.The algorithms’ analyses use approximate matrix product sketch guarantees rather than density of the JL distribution.
- Implementation considerations: The algorithms ignore hash-function storage and evaluation costs initially, then address evaluation using fast multipoint polynomial evaluation.The implementation discussion explains why direct t-wise independent hash evaluation could introduce factors such as n or r.
- Linear regression: Linear regression supports a one-pass turnstile algorithm with sketch size O(n^2ε^-1 log(1/δ) log(nd)).The algorithm processes updates using the sparse JL sketch while targeting a (1+ε)-approximation to the least-squares residual.
- Low rank approximation: Low-rank approximation supports a one-pass row/column-update algorithm with sketch size O(rε^-1(n+d) log(1/δ) log(nd)).The maintained sketch supports approximation relative to the best rank-r error under the stated precision and update setting.
- Low rank approximation: The low-rank algorithm requires r/ε · log(1/δ) amortized arithmetic operations and hash evaluations per matrix entry.This improves the amortized update complexity O(rε^-1 log(1/δ)) reported for prior work.
7 Open Problems
The paper identifies unresolved tightness questions for sparse JL constructions and metric JL, focusing on logarithmic gaps in sparsity and dimension lower bounds. It also presents a conjecture comparing the error distributions of two sparse constructions.
- Conjectures on sparse constructions: The graph construction’s fixed number of nonzeros per column is conjectured to outperform Achlioptas’s random normalized sign construction in a stronger stochastic sense.The conjecture compares the absolute norm-preservation errors ZA and ZG for the two constructions.
- Conjectures on sparse constructions: A positive resolution would establish stronger performance for the graph construction beyond its better asymptotic sparsity bound.The paper frames this as a definitive comparison with the Achlioptas construction.
- Metric JL: For metric JL, the paper reports that both the row and sparsity lower bounds remain within O(log(1/ε)) factors of the known constructions.Its construction achieves at most O(ε^-1 log n) nonzeros per column while using O(ε^-2 log n) rows.
- Open lower-bound question: The paper asks whether distributional JL requires the tight lower bound s = Ω(ε^-1 log(1/δ)) when k = O(ε^-2 log(1/δ)) < d/2.Resolving this would remove the remaining O(log(1/ε)) factor gap.