Combining geometry and combinatorics: A unified approach to sparse signal recovery

By Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard J. Karloff, Martin J. Strauss. 2008 46th Annual Allerton Conference on Communication, Control, and Computing, 2008

451 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e9415d34745bd4a5c5c484b83b007cb711693ecb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Signal Processing

Citations in the corpus

Compressed Sensing for Real-Time Energy-Efficient ECG Compression on Wireless Body Sensor Nodes (2011, background): “it was proven in Theorem 2 of [35] that the RIP1 property of a sparse binary sensing matrix with exactly d ones on each row”
Inverting Deep Generative models, One layer at a time (2019, background): “For instance, studies in [3] showed that a (scaled) random sparse binary matrix with m = O ( s log( k/s ) / 2 ) rows is ( s, 1 + (cid:15) ) -RIP-1 with high probability.”
Sparse Recovery Using Sparse Matrices (2010, methodology): “One such property is based on the notion of graph expansion [ 2 ], [44].”
A Nonparametric Approach to Modeling Choice with Limited Data (2009, methodology): “• In the context of streaming algorithms through the design of ‘sketches’ (see Tropp (2006, 2004), Berinde et al. (2008), Cormode and Muthukrishnan (2006), Gilbert et al.”
Efficient and reliable low-power backscatter networks (2012, methodology): “In our implementation, we use an algorithm based on the interior-point method [22] 4 , which has the running time of T = O ( I · T A ′ ) , where I ≈ √ aK is the number of iterations in the algorithm, and T A ′ is the cost of a matrix-vector multiplication involving A ′ [4].”
Provable Bounds for Learning Some Deep Representations (2013, background): “Usually one imagines that NP-hardness is not a barrier to provable algorithms in ML because the inputs to the learner are drawn from some simple distribution and are not worst-case.”
Solving inverse problems using data-driven models (2019, unknown): “This class of approaches includes Fourier sampling, chaining pursuit and HHS pursuit (Berinde et al. 2008).”
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming (2011, methodology): “Having said this, we note that RIP-1 properties have also been used in the compressed sensing literature, see [6] for example.”
A sparse Johnson: Lindenstrauss transform (2010, unknown): “In a similar vein, Berinde et al. [10] use an unbalanced expander graph based construction to create matrices with restricted isometry property for sparse signal recovery.”