Sparser Johnson-Lindenstrauss Transforms

By Daniel M. Kane, Jelani Nelson. ACM-SIAM Symposium on Discrete Algorithms, 2010

397 citations recorded by the source corpus.

We give two different and simple constructions for dimensionality reduction in ℓ2 via linear mappings that are sparse: only an O(ε)-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1 + ε 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 [2003] and Dasgupta et al. [2010]. Such distributions can be used to speed up applications where ℓ2 dimensionality reduction is used.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/96284943dcbd05aba9464b8cfe68fd9040cc16ec

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 Computer Vision and Pattern Recognition

Citations in the corpus

Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, methodology): “Here we describe a construction given by [25, 19].”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, methodology): “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].”
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.”
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): “Chapter Overview: In §3.1 we show how one can adapt the idea of leverage score sampling in §2.4 for ℓ2 to provide an initial samplingbased algorithm for ℓ1-regression.”
Distance geometry and data science (2019, methodology): “sults. 5.Surprisingly, the target dimension kis independent of the original dimension n. 6.Even if the data in Xis sparse, TXends up being dense. Dierent classes of sparse RPs have been investigated [2, 96] in order to tackle this issue. A simple algorithm [53, x5.1] consists in initializing Tas the”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “In fact, we instead follow a simpler and slightly tighter analysis of Kane and Nelson [2012] based on the Hanson-Wright inequality.”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, methodology): “For example, we may use the dense Rademacher matrix distribution of family 1 of Lemma 11, or a sparse family such as those given in [29].”