Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit

By Deanna Needell, Roman Vershynin. Foundations of Computational Mathematics, 2007

1,034 citations recorded by the source corpus.

This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements—L1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of L1-minimization. Our algorithm, ROMP, reconstructs a sparse signal in a number of iterations linear in the sparsity, and the reconstruction is exact provided the linear measurements satisfy the uniform uncertainty principle.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics

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

How researchers see this paper

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

Citations in the corpus

SPARSE RECONSTRUCTION FOR SAR IMAGING BASED ON COMPRESSED SENSING (2010, neutral): “Such algorithms include basis pursuit (BP) [19], orthogonal match-pursuit (OMP) [20] and regularized orthogonal matching pursuit (ROMP) [21].”
Learning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization (2009, methodology): “We start by reviewing prior related work, following by the presentation of our proposed algorithm and the first results showing the computational and reconstruction advantages of this new approach.”
Compressive sensing: From theory to applications, a survey (2013, methodology): “For such situations, improved versions of OMP have been devised like regularized OMP [33], stagewise OMP [34], compressive sampling matching pursuits (CoSaMP) [35], subspace pursuits [36], gradient pursuits [37], and orthogonal multiple matching pursuit [38].”
Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity (2008, background): “The first part of the claim, as well as a related modification of the second claim also appeared in [4], [11].”
Compressed Sensing (2014, neutral): “Una primer opción, que no será analizada en este trabajo, es utilizar algoritmos de tipo “Greedy”, entre los que destacan: “Orthogonal Matching Pursuit (OMP)” [58], OMP Regularizado (ROMP) [54], “Iterative hard thresholding (IHT)” [10] y “Compressive Sampling Matching Pursuit” (CoSaMP) [53].”
Compressed Sensing (2012, background): “Other prominent examples of greedy algorithms are stagewise OMP (StOMP) [28], regularized OMP (ROMP) [51], and compressive sampling MP (CoSamp) [50].”
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, methodology): “Let M T 0 = C T 0 Σ T 0 D T T 0 be the Singular Value Decomposition (SVD) of M T 0 . f f Updates of the form (2.1) have a long history in compressed sensing/matrix sensing literature (see e.g. [TG07, GK09, NT09, NV09, BD09, MJD09, CCS10]).”
Compressive Sensing with structured random matrices (2012, background): “We will concentrate here on the latter and refer the reader to the literature [40, 58, 78, 90, 91, 103, 131, 127] for further information concerning greedy methods.”
Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property (2009, methodology): “Moreover, the fact that our bound requires only the RIP of order K +1 is apparently unique among the published CS literature; much more common are results requiring the RIP of order 1.75K [12], 2K [11, 13], 3K [16, 18], 4K [15], and so on.”
Combining geometry and combinatorics: A unified approach to sparse signal recovery (2008, methodology): “Speciﬁcally, the papers [NV07, DM08, NT08] show that one can use greedy methods for data compressed using dense matrices satisfying the RIP property.”
Signal Processing With Compressive Measurements (2010, background): “Thus, up to this point, most of the CS literature has focused on improving the speed and accuracy of this process [6]–[9].”