Random matrices for compressive sensing

In compressive sensing, the sampling process is replaced by a "measurement matrix".  One of the more surprising aspects of compressive sensing is that one can generate a measurement matrix at random (where the entries are drawn from an appropriate distribution), and with overwhelming probability, that matrix will work.  While this may seem surprising, it has been known for some time that these same random matrices are useful for dimensionality-reduction. In particular, recent proofs of the Johnson-Lindenstrauss lemma use random matrices to show that we can map a set of p points into O(log(p)) dimensions without disturbing the inter-point distances. We show how recent simple proofs of the Johnson-Lindenstrauss lemma provide elegant proofs of two fundamental results in compressive sensing and n-widths. Our elementary approach is based on the same concentration inequalities for random inner products used in the proofs of the Johnson-Lindenstrauss lemma. We show how these ideas lead to simple proofs of Kashin's theorems on widths of finite balls in Euclidean space (and their improvements due to Gluskin) as well as the existence of optimal measurement matrices. In the process we also prove that these measurement matrices are universal with respect to the sparsity inducing basis.

Authors: Richard Baraniuk, Mark Davenport, Ronald DeVore, Michael Wakin

Publications: Constructive Approximation 2008

Related research at Rice