The road to deterministic matrices with the restricted isometry property

Compressed sensing is all about hitting sparse vectors with short, fat matrices.  Specifically, we want to be able to efficiently and stably recover any sparse vector from a corresponding matrix-vector product.  I recently wrote a paper that discusses how one might design matrices with this particular application in mind:

To reconstruct a sparse vector x from relatively few measurements y=\Phi x, it has become popular to find an estimate \hat{x} of minimal 1-norm.  This estimate happens to be the sparsest vector in the preimage of y provided \Phi satisfies the restricted isometry property (RIP).  In words, an RIP matrix acts as a near-isometry on sufficiently sparse vectors, and since its introduction in 2004, this property has become an important subject of matrix design (see Terry Tao’s blog post on the problem).

To date, the best known RIP matrices are constructed using random processes, while deterministic constructions have found less success.  This paper considers various methods for demonstrating RIP deterministically, and it makes some interesting connections with graph theory and number theory.

One thought on “The road to deterministic matrices with the restricted isometry property

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s