Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit

By Deanna Needell, Roman Vershynin. IEEE Journal on Selected Topics in Signal Processing, 2007

948 citations recorded by the source corpus.

We demonstrate a simple greedy algorithm that can reliably recover a vector v ¿ ¿d from incomplete and inaccurate measurements x = ¿v + e. Here, ¿ is a N x d measurement matrix with N<<d, and e is an error vector. Our algorithm, Regularized Orthogonal Matching Pursuit (ROMP), seeks to provide the benefits of the two major approaches to sparse recovery. It combines the speed and ease of implementation of the greedy methods with the strong guarantees of the convex programming methods. For any measurement matrix ¿ that satisfies a quantitative restricted isometry principle, ROMP recovers a signal v with O(n) nonzeros from its inaccurate measurements x in at most n iterations, where each iteration amounts to solving a least squares problem. The noise level of the recovery is proportional to ¿{logn} ||e||2. In particular, if the error term e vanishes the reconstruction is exact.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

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

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Subspace Pursuit for Compressive Sensing Signal Reconstruction (2008, neutral): “The proof of Corollary 1 is based on the following two lemmas, which are proved in [21] and [22], respectively.”
Iterative Hard Thresholding for Compressed Sensing (2008, background): “This property of many signals is exploited in compressed sensing.”
A Systematic Review of Compressive Sensing: Concepts, Implementations and Applications (2018, background): “There is a rich literature on CS reconstruction algorithms, improving further upon the algorithms like OMP, AMP, weighted `1 and others [49]–[52].”
Generalized Orthogonal Matching Pursuit (2011, methodology): “In order to observe the effect of K on the complexity, we measure the running time of the OMP as a function of n for three distinct sparsity levels ( = 0 .”
Advances on Spectrum Sensing for Cognitive Radio Networks: Theory and Applications (2017, methodology): “These ca be listed as the regularized orthogonal matching pursuit (ROMP) [119], the compressive sampling matching pursuit (CoSaMP) [110], subspace pursuit (SP) [112], the treebased orthogonal matching pursuit (TOMP) [111].”
Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity (2008, background): “Recovery Distortion under Signal and Measurement Perturbations The proof of Corollary 1 is based on the following two lemmas, which are proved in [16] and [17], respectively.”
Sparsity adaptive matching pursuit algorithm for practical compressed sensing (2008, background): “Index Terms— Sparsity adaptive, greedy pursuit, compressed sensing, compressive sampling, sparse reconstruction”
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing (2009, positive): “Popular methods have been developed from many viewpoints: `1minimization [1], [2], [3], [4], [5], [6], matching pursuit [7], [8], [9], [10], iterative thresholding methods [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], subspace methods [10], [21], [20], [22], convex regularization [23],”
Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property (2009, methodology): “However, several alternative greedy algorithms have been proposed—all essentially modifications of OMP—that are apparently much more amenable to RIP-based analysis.”
A non-adapted sparse approximation of PDEs with stochastic inputs (2010, methodology): “Some of the standard greedy pursuit algorithms are Orthogonal Marching Pursuit (OMP) [55,27], Regularized OMP (ROMP)[49], Stagewise OMP (StOMP) [31], Compressive Sampling MP (CoSaMP) [48], Subspace Pursuit [24], and Iterative Hard Thresholding (IHT) [26].”
Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals (2009, background): “Both these numbers range between zero and one.”
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples (2008, positive): “Very recently, Needell and Vershynin developed and analyzed another greedy approach, called regularized OMP , or ROMP [28, 27].”
$L_{1/2}$ Regularization: A Thresholding Representation Theory and a Fast Solver (2012, neutral): “The greedy strategies, such as the matching pursuit type of algorithms [28], OMP [29], ROMP [30], are very fast for non-highdimensional problems [31], [32].”