Combining geometry and combinatorics: A unified approach to sparse signal recovery
Authors:
- 1 September 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 798-805
Abstract
There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach utilizes geometric properties of the measurement matrix Phi. A notable example is the Restricted Isometry Property, which states that the mapping Phi preserves the Euclidean norm of sparse signals; it is known that random dense matrices satisfy this constraint with high probability. On the other hand, the combinatorial approach utilizes sparse matrices, interpreted as adjacency matrices of sparse (possibly random) graphs, and uses combinatorial techniques to recover an approximation to the signal. In this paper we present a unification of these two approaches. To this end, we extend the notion of Restricted Isometry Property from the Euclidean lscr2 norm to the Manhattan lscr1 norm. Then we show that this new lscr1 -based property is essentially equivalent to the combinatorial notion of expansion of the sparse graph underlying the measurement matrix. At the same time we show that the new property suffices to guarantee correctness of both geometric and combinatorial recovery algorithms. As a result, we obtain new measurement matrix constructions and algorithms for signal recovery which, compared to previous algorithms, are superior in either the number of measurements or computational efficiency of decoders.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Bayesian Compressive Sensing Via Belief PropagationIEEE Transactions on Signal Processing, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Single-pixel imaging via compressive samplingIEEE Signal Processing Magazine, 2008
- The price of privacy and the limits of LP decoding2007
- Sudocodes ߝ Fast Measurement and Reconstruction of Sparse Signals2006
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Thresholds for the Recovery of Sparse Solutions via L1 Minimization2006
- High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to DimensionDiscrete & Computational Geometry, 2005
- New directions in traffic measurement and accountingACM Transactions on Computer Systems, 2003
- Nonlinear Methods of ApproximationFoundations of Computational Mathematics, 2003