A sparse Johnson: Lindenstrauss transform

By Anirban Dasgupta, Ravi Kumar, Tamás Sarlós. 2010

223 citations recorded by the source corpus.

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 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 ~O(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 Ω(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 ~O(1/ε) update time per non-zero element for a (1 ε)-approximate projection, thereby substantially outperforming the ~O(1/ε2) update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its ~O(d) worst case running time matches the best approach of Ailon and Liberty.

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Signal Processing

Citations in the corpus

Compressing Convolutional Neural Networks in the Frequency Domain (2015, methodology): “a the hashing trick) [11, 49, 60] has been previously studied as a technique for reducing model storage size.”
Privacy via the Johnson-Lindenstrauss Transform (2012, background): “The extremely sparse projection matrix of Dasgupta et al. [9].”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, neutral): “− However, we are not certain whether the same results hold for sparse transforms (see [DKS10]).”
Consistent Weighted Sampling Made Fast, Small, and Easy (2014, methodology): “requires time O(nk) to generate k samples, recent work on fast Johnson-Lindenstrauss lemma [1, 2, 9] may be viewed as giving faster algorithms for SimHash.”
Random Projections, Graph Sparsification, and Differential Privacy (2013, background): “The famous JL transform [1, 2, 5, 6, 21, 22] can be seen as a random projection of d points from a n-dimensional space to a lower dimensional space such that the Euclidean distance between any two pairs of points is maintained.”
Handbook of Big Data (2016, methodology): “Another approach is also to use a carefully designed sparse matrix A [40].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “The ﬁrst idea for bringing this down is that the analysis of Dasgupta et al. [2010] can itself be tightened by applying it on vectors coming from a subspace instead of on a set of arbitrary vectors.”
Unifying Orthogonal Monte Carlo Methods (2019, methodology): “Several improvements on the JLT have been proposed, yielding computational ben-eﬁts (Ailon & Chazelle, 2009; Dasgupta et al., 2010).”
Sparser Johnson-Lindenstrauss Transforms (2010, background): “Figure (a) is the DKS construction in [10], and the two constructions we give in this work are represented in (b) and (c).”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, background): “There have been two popular lines of work in this area: one focusing on fast embeddings for all vectors [2]–[4], [19], [24], [25], [37], and one focusing on fast embeddings specifically for sparse vectors [1], [6], [13], [21], [22].”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, unknown): “We note that stronger embedding results are known with fewer bits, if one imposes restrictions on the ℓ ∞ norm of the vectors x ∈ E to be embedded – see [29] and [14].”
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, background): “Several works developed sparse JL embeddings [1, 9, 19] and sparse subspace embeddings [25].”
Sketch-Based Linear Value Function Approximation (2012, background): “Our bound relies on interpreting tug-of-war hashing as a special kind of Johnson-Lindenstrauss transform [8].”
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering (2018, background): “…satisfy a variant of Theorem 1.1 (sometimes with somewhat worse bound on d ) but do not necessarily satisfy Deﬁnition 1.2: most notably, “sparse” constructions [DKS10, KN14] as well as “fast” constructions based on sub-sampled randomized Fourier-like transforms [AC06, AL09, KW11, AL13, NPW14].”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “bility 2/3. The latter is important since it results in a sparse matrix S, for which one can then compute S ·x for a vector x ∈Rn more quickly. A breakthrough was made by Dasgupta, Kumar, and Sa´rlos [33] who showed that it suﬃces for each column of S to have only ε−1poly(log(f/δ)) non-zero entries ”