|
abstract:
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 l_1-minimization.
Consider an m x N matrix satisfying the (k, &delta _k)-RIP with randomized column signs and an arbitrary set E of O(e^k) points in R^N. We show that with high probability, such a matrix with randomized column signs maps E into R^m without distorting the distance between any two points by more than a factor of 1 +/- 4 &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 yield new Johnson-Lindenstrauss bounds for several deterministic matrices with randomized column signs.
This is joint work with Rachel Ward. |
