Johnson-Lindenstrauss and RIP September 10, 2010

Posted by Sarah in Uncategorized.
Tags: ,

Via Nuit Blanche, I found a paper relating the Johnson-Lindenstrauss Theorem to the Restricted Isometry Property (RIP.) It caught my eye because the authors are Rachel Ward and Felix Krahmer, whom I actually know! I met Rachel when I was an undergrad and she was a grad student. We taught high school girls together and climbed mountains in Park City, where I also met Felix.

The Johnson-Lindenstrauss Lemma says that any p points in n-dimensional Euclidean space can be embedded in $O(\epsilon^{-2} \log(p))$ dimensions, without distorting the distance between any two points by a distance of more than a factor between $(1 -\epsilon)$ and $(1 + \epsilon)$. So it gives us almost-isometric embeddings of high-dimensional data in lower dimensions.

The Restricted Isometry Property, familiar to students of compressed sensing, is the property of a matrix $\Phi$ that

$(1-\delta) ||x||_2^2 \le ||\Phi x||_2^2 \le (1 + \delta) ||x||_2^2$
for all sufficiently sparse vectors $x$.
The relevance of this property is that these are the matrices for which $\ell_1$-minimization actually yields the sparsest vector — that is, RIP is a sufficient condition for basis pursuit to work.

Now these two concepts involve equations that look a lot alike… and it turns out that they actually are related. The authors show that RIP matrices produce Johnson-Lindenstrauss embeddings. In particular, they produce improved Johnson-Lindenstrauss bounds for special types of matrices with known RIP bounds.

The proof relies upon Rademacher sequences (uniformly distributed in [-1, 1]), which I don’t know a lot about, but should probably learn.

[N.B.: corrections from the original post come from Felix.]

1. Igor Carron - September 13, 2010

Sarah,

You said “RIP is a necessary condition for basis pursuit to work”. As far as I know, RIP is really a sufficient condition for basis pursuit.

Cheers,

Igor.

2. Sarah - September 15, 2010

Oops, sorry!