Graduate Student / Postdoc Seminar

New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property

Speaker: Felix Krahmer, Hausdorff Center for Mathematics, University of Bonn

Location: Warren Weaver Hall 1302

Date: Friday, March 25, 2011, 1 p.m.

Synopsis:

The Johnson-Lindenstrauss (JL) Lemma states that any set of $$p$$ points in high dimensional Euclidean space can be embedded into $$O(\delta^{-2}\log(p))$$ dimensions, without distorting the distance between any two points by more than a factor between $$1-\delta$$ and $$1+\delta$$. We establish a new connection between the JL Lemma and the Restricted Isometry Property (RIP), a well-known concept in the theory of sparse recovery often used for showing the success of $$\ell_1$$-minimization.

Consider an $$m \times N$$ matrix satisfying the $$(k,\delta_{k})$$-RIP with randomized column signs and an arbitrary set $$E$$ of $$O(e^k)$$ points in $$\mathbb{R}^N$$. We show that with high probability, such a matrix with randomized column signs maps $$E$$ into $$\mathbb{R}^m$$ without distorting the distance between any two points by more than a factor of $$1\pm4\delta_k$$. Consequently, matrices satisfying the Restricted Isometry of optimal order provide optimal Johnson-Lindenstrauss embeddings up to a logarithmic factor in $$N$$. Moreover, our results yield the best known bounds on the necessary embedding dimension $$m$$ for a wide class of structured random matrices. In particular, for partial Fourier and partial Hadamard matrices, our method optimizes the dependence of $$m$$ on the distortion $$\delta$$ : We improve the recent bound $$m = O(\delta^{-4}\log(p)\log^4(N))$$ of Ailon and Liberty (2010) 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.

This is joint work with Rachel Ward.