There are two main algorithmic approaches to sparse signal ecovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix Phi and then uses linear programming to decode information about x from Phi x. The combinatorial approach constructs Phi and a
combinatorial decoding algorithm to match.
We present a unified approach to these two classes of sparse signal recovery algorithms. The unifying elements are the adjacency
matrices of high-quality unbalanced expanders. We generalize the notion of Restricted Isometry Property (RIP), crucial to compressed
sensing results for signal recovery, from the Euclidean norm to the ell-p norm for p approximately 1, and then show that unbalanced expanders are essentially equivalent to RIP-p matrices. From known deterministic constructions for such matrices, we obtain new deterministic measurement matrix constructions and algorithms
for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.
Authors: R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, and M. J. Strauss
Copyright. All Rights Reserved.