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.