New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property

By Felix Krahmer, Rachel A. Ward. SIAM Journal on Mathematical Analysis, 2010

316 citations recorded by the source corpus.

Consider an m by N matrix Phi with the Restricted Isometry Property of order k and level delta, that is, the norm of any k-sparse vector in R^N is preserved to within a multiplicative factor of 1 +- delta under application of Phi. We show that by randomizing the column signs of such a matrix Phi, the resulting map with high probability embeds any fixed set of p = O(e^k) points in R^N into R^m without distorting the norm of any point in the set by more than a factor of 1 +- delta. Consequently, matrices with the Restricted Isometry Property and with randomized column signs provide optimal Johnson-Lindenstrauss embeddings up to logarithmic factors in N. In particular, our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices; for partial Fourier and partial Hadamard matrices, we improve the recent bound m = O(delta^(-4) log(p) log^4(N)) appearing in Ailon and Liberty to m = O(delta^(-2) log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries.

Subfields: Applied Mathematics, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/e5d3ee26131badea6e308294b80b05c9e3661e9c

How researchers see this paper

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

In Applied Mathematics

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

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].”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Embedding properties of an SRTT for general sets follow from (Rudelson and Vershynin 2008) and (Krahmer and Ward 2011); see Foucart and Rauhut (2013, Chap.”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, result): “In the ROS case, results of Krahmer and Ward [18] imply that”
Sparser Johnson-Lindenstrauss Transforms (2010, background): “Several works have devised other distributions which give faster embedding times [2, 3, 4, 14, 23, 31], but all these methods require Ω(d) embedding time even for sparse vectors (even when ‖x‖0 = 1).”
Circulant Binary Embedding (2014, methodology): “The advantage is to save on storage allowing even large scale datasets to fit in memory (Li et al., 2011; Sánchez & Perronnin, 2011).”
Improved Analysis of the subsampled Randomized Hadamard Transform (2010, background): “The literature already contains a number of papers, including [AC09, Lib09, NDT09, HMT11, AL11, KW11], that study the behavior of the SRHT and related dimension reduction maps.”
Compressed Sensing (2012, result): “We also mention that recently even a converse of the following theorem was proved in [40].”
Intermediate Layer Optimization for Inverse Problems using Deep Generative Models (2021, methodology): “The proof follows from the proof of Lemma 3 above and Theorem 3.1 in (Krahmer & Ward, 2011).”
An investigation of Newton-Sketch and subsampled Newton methods (2017, unknown): “We follow [10, 16] and define the Hadamard matrices H ∈ Rn×n as having entries |Hi,j | ∈ [ −1 √ n , 1 √ n ] .”