There are two main algorithmic approaches to sparse signal recovery:
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 {\em
unbalanced expanders}.  We generalize the notion of {\em restricted
isometry property} (RIP), crucial to compressed sensing results for
signal recovery, from the Euclidean norm to the $\ell_p$ norm for $p >
1$, and then show that unbalanced expanders are essentially equivalent
to RIP-$p$ matrices.

From known deterministic constructions for such matrices, we obtain
new {\em 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.
