Source-linked AI summary
A Sparse Johnson--Lindenstrauss Transform
Anirban Dasgupta, Ravi Kumar, Tamás Sarlós
TL;DR
The paper addresses how to make Johnson–Lindenstrauss dimension reduction sparse and faster, especially for sparse inputs. It uses hash-based projection construction and local densification, obtaining sparse matrices and improved update-time guarantees while retaining projection properties.
Problem
Dimension reduction is widely useful, but prior sparse projection constructions and fast transforms impose sparsity or running-time limitations, especially for sparse vectors.
Method
The paper constructs the projection matrix with hash-function dependencies, fixed non-zero counts per column, and preconditioning variants for sparse inputs.
Results
The construction achieves O( 1 ǫ2 ) non-zero entries in the projection matrix and an update time of ˜O( 1 ǫ per non-zero element, while a variant improves sparse-vector running time.
Takeaways & Limitations
Hash-based dependencies and local densification provide a sparse projection approach that can exploit input sparsity and improve over global-Hadamard methods for sparse vectors.
Takeaways & Limitations
Applying the results to streaming requires proving claims for limited-independence hash functions and ±1 variables; efficient derandomization remains open.
Abstract
from arXiv · showhide
Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work we obtain a {\em sparse} version of the fundamental tool in dimension reduction --- the Johnson--Lindenstrauss transform. Using hashing and local densification, we construct a sparse projection matrix with just $\tilde{O}(\frac{1}ε)$ non-zero entries per column. We also show a matching lower bound on the sparsity for a large class of projection matrices. Our bounds are somewhat surprising, given the known lower bounds of $Ω(\frac{1}{ε^2})$ both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions. Using this, we achieve an $\tilde{O}(\frac{1}ε)$ update time per non-zero element for a $(1\pmε)$-approximate projection, thereby substantially outperforming the $\tilde{O}(\frac{1}{ε^2})$ update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its $\tilde{O}(d)$ worst case running time matches the best approach of Ailon and Liberty.
1. INTRODUCTION
The paper develops a sparse Johnson–Lindenstrauss projection using hash-based dependencies and local densification, reducing computational costs while preserving projection guarantees. It also compares this approach with prior sparsity bounds and fast transforms.
- Dimension reduction supports applications including nearest-neighbor search, compressed sensing, streaming computations, numerical linear algebra, machine learning, and graph sparsification.
- The hash-based projection constructs exactly a fixed number of non-zero entries in each column, relaxing requirements on input-vector density.The construction introduces dependencies among matrix entries rather than using independent random variables.
- The approach requires only ∥x∥∞= O(√ for the stated sparsity regime, whereas prior work requires ∥x∥∞= O(ǫ).
- The analysis bounds each hash bucket's contribution and collision noise, while avoiding self-collisions reduces the variance of cross-product error.The choice of ±1 random variables instead of Gaussian variables is critical to the proofs.
- Unlike global-Hadamard approaches requiring ˜O(d) time per streaming update, the proposed update time is only ˜O( 1 ǫ .
- The resulting methods improve running time for sparse vectors, including nearest-neighbor computation, with effective costs stated in terms of nnz(x).A block-Hadamard preconditioner yields a running time of ˜O(min( nnz ǫ , d)).
2. MAIN RESULTS
The main results use hash-based matrices and preconditioners to obtain norm-preserving projections with controlled sparsity and running time. The construction provides guarantees for individual vectors and a preconditioned variant for all vectors.
- Projection guarantee: Theorem 1 gives a probability 1 − 4δ projection guarantee for any given input vector x.The theorem states that Φ satisfies the required property for a specified vector.
- Hash-based construction: The hash-based matrix H has exactly one non-zero entry per column.H is formed from a uniformly random hash function and independent random signs.
- Preconditioned projection: A modified preconditioner guarantees O(d log c log log c) running time for all vectors.The construction is based on a randomized Hadamard preconditioner.
- Preconditioned projection: The preconditioned transform (HG)x has an explicitly analyzed computation time.The section introduces the time required to compute (HG)x after stating the norm-preservation guarantee.
3. PROOF OF THEOREM 2
The proof controls the deviation of the projected norm by analyzing hash-bucket cross-products, first conditioning on good hash functions and then handling dependence across buckets with the FKG inequality.
- Randomness and concentration: The proof relies critically on independent ±1 random variables, whose cross-products cancel in expectation and support the concentration analysis.The analysis also uses Bernstein's inequality and a weighted balls-into-bins load bound.
- Proof strategy: Each coordinate maps to exactly one hash bucket, so the projected norm error reduces to concentration of the sum of bucket-level variables.The lack of self-collisions reduces cross-product variance relative to i.i.d. matrix entries.
- Proof strategy: Most hash functions are good, and for a fixed hash function the proof bounds each bucket variable's moment generating function.Goodness controls bucket loads and enables expected and worst-case MGF bounds.
- Proof strategy: The proof uses truncated variables defined through hash-function goodness rather than directly truncating the random signs.Direct truncation would introduce dependence between the sign and hash variables and obstruct the FKG argument.
- Conclusion: The resulting MGF bounds yield upper and lower tail bounds for the total error, which are combined to obtain concentration around zero.The argument applies Theorem 11 and then derives the main theorems from it.
- Handling dependence: The FKG inequality bounds the MGF of the sum of dependent bucket variables by the product of their individual MGFs.The auxiliary functions are constructed as increasing and decreasing set functions, satisfying the monotonicity requirements of FKG.
4. PROOF OF THEOREM 3
For sparse inputs, the paper uses block-diagonal randomized Hadamard preconditioning before hashing, preserving the approximation guarantee while limiting computation to blocks touched by nonzero coordinates.
- Block-Hadamard preconditioning: A randomized Hadamard matrix is applied independently within each diagonal block of a block-diagonal preconditioner.Each block is an isometry, so the transformation preserves the ℓ2 norm within the block.
- Block-Hadamard preconditioning: The block size is chosen as b = 6c log(3c/δ), subject to b ≤ d, to control the preconditioned vector's blockwise concentration.Because the input has unit norm, only a limited number of blocks can have large input norm.
- Guarantee: The ε-approximation guarantee follows from combining the block-Hadamard lemma with the sparse projection theorem.The preconditioner supplies the required density condition for the subsequent projection.
- Running time: The running time is O(nnzb(x)·b log b + nnzb(x)·b), where nnzb(x) counts blocks containing nonzero coordinates.The computation depends on the number of touched blocks rather than directly on all d coordinates.
- Comparison and boundary: When δ is not too small, the method matches the best existing dense-vector running times while being much faster for sparse vectors.Combining the preconditioner with larger-block sparse matrices would reproduce prior dense-vector results but would not improve sparse-vector update time.
5. A LOWER BOUND
The lower-bound argument studies projection matrices whose support is selected first and whose nonzero entries are randomized afterward, showing that sparsity must grow with the distortion parameter under mild moment conditions.
- Lower-bound model: The lower-bound construction separates support selection from independent randomization of the columns, without requiring independence among entries within a column.The support matrix may be fixed or random, while each column is then sampled independently.
- Pairwise overlap: For vectors e_i + e_j, the JL property constrains pairwise overlaps between the nonzero supports of columns i and j.The proof uses fourth-moment deviations of overlap-dependent random variables.
- Pairwise overlap: The overlap bound |C_i ∩ C_j| ≤ 16ε^2c^2 implies c ≥ 1/(16ε) when supports would otherwise be disjoint.If the overlap threshold is below one, pairwise disjointness forces k ≥ dc, contradicting k < d.
- Strengthened bound: A set-packing argument strengthens the lower bound to log_k(d) − 3 ≤ 16ε^2c^2 over a large range of d and k.This follows by bounding the number of distinct column supports with limited pairwise intersections.
- Scope and consequence: Under mild technical conditions, the lower bound applies to independent scaled ±1 entries and replicated hashing, making the sparse upper bound tight in ε.The resulting per-column sparsity bound also gives a worst-case update-time bound.
- Average sparsity: When the fourth moment scales with the number of nonzeros per column, the argument bounds the average number of nonzeros per column as well.Independent scaled ±1 random variables satisfy this moment condition.
6. EMBEDDING INTO ℓ1
The paper constructs an ℓ1 embedding using hash-based random variables and Gaussian coefficients, obtaining a concentration guarantee for the normalized summed absolute bucket outputs. The proof is omitted in this version.
- Construction: The matrix H is defined by Hij = δih(j)rj, with independent Gaussian coefficients rj ∼ N(0,1).The construction targets the ℓ1 metric and uses the 2-stability of the normal distribution.
- Construction: β0 is defined as E[|z|] for z ∼ N(0,1), and the bucket outputs Yi are analyzed through Gaussian stability.
- Guarantee: For c = k/ε and k = O(...), Theorem 16 gives Pr[|Y − 1| > ε] < δ for sufficiently small ε.The supplied theorem statement truncates the condition on k.
- Proof status: The proof of the ℓ1 result is omitted in this version.
7. DISCUSSIONS
The discussion identifies unresolved error-probability bounds and derandomization challenges for streaming, while relating the hash function to expander-based sparse-recovery constructions. It also notes a possible connection to prior work using ℓ1 error and sparse inputs.
- Open questions: The main open question is closing the gap between the upper and lower bounds on error probability.
- Streaming limitations: Applying the result to streaming requires proofs for k-wise independent hash functions and ±1 variables.The FKG inequality in the limited-independence setting is identified as a chief hurdle.
- Streaming limitations: Nisan’s generator can derandomize the hash function, but the naive approach increases update time to k; efficient derandomization remains open.
- Connections: The hash function represents a bipartite expander, connecting the construction to expander-based restricted-isometry matrices for sparse signal recovery.The related argument relies on ℓ1 error norms and sparse input vectors.
9. APPENDIX
The appendix develops concentration and monotonicity arguments for the hashed projection, including moment-generating-function bounds, Bernstein optimization, and an omitted proof for part of Theorem 11.
- Concentration analysis: The appendix bounds tail probabilities using moment-generating functions, Markov’s inequality, and Bernstein’s inequality.It first computes conditional MGF expectations under different hashing conditions.
- Monotonicity argument: The proof establishes that gs is decreasing by comparing conditional expectations across hash assignments and showing EL ≥ ER.The comparison uses case analysis for good and bad hash buckets.
- Parameter choice: The Bernstein calculation restricts u < 1 and selects u by setting the derivative of the bounding function to zero.The resulting bound is simplified using a standard Bernstein inequality estimate.
- Proof status: The proof of Theorem 11(ii) is omitted in this version.