##
Johnson-Lindenstrauss and RIP *September 10, 2010*

*Posted by Sarah in Uncategorized.*

Tags: compressed sensing, dimensionality reduction

trackback

Tags: compressed sensing, dimensionality reduction

trackback

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.

So what’s this all about?

The Johnson-Lindenstrauss Lemma says that any p points in n-dimensional Euclidean space can be embedded in dimensions, without distorting the distance between any two points by a distance of more than a factor between and . 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 that

for all sufficiently sparse vectors .

The relevance of this property is that these are the matrices for which -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.]

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.

Oops, sorry!