Compressed Sensing: Sparse Measurement Matrices

Radu Berinde and Piotr Indyk just released Sparse Recovery Using Sparse Random Matrices ( a newer version of this paper is at MIT-CSAIL-TR-2008-001 while an implementation of these matrices is here). The abstract reads:

We consider the approximate sparse recovery problem, where the goal is to (approximately) recover a high-dimensional vector x from its lower-dimensional sketch Ax. A popular way of performing this recovery is by finding x# such that Ax = Ax#, and |x#|_1 is minimal. It is known that this approach “works” if A is a random dense matrix, chosen from a proper distribution. In this paper, we investigate this procedure for the case where A is binary and very sparse. We show that, both in theory and in practice, sparse matrices are essentially as “good” as the dense ones. At the same time, sparse binary matrices provide additional benefits, such as reduced encoding and decoding time.

Wow. Simple sparse measurement matrices, I know a few people who are going to be happy.