Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property

By Mark A. Davenport, Michael B. Wakin. IEEE Transactions on Information Theory, 2009

547 citations recorded by the source corpus.

Orthogonal matching pursuit (OMP) is the canonical greedy algorithm for sparse approximation. In this paper we demonstrate that the restricted isometry property (RIP) can be used for a very straightforward analysis of OMP. Our main conclusion is that the RIP of order K+1 (with isometry constant δ <; [ 1/( 3√K)]) is sufficient for OMP to exactly recover any K-sparse signal. The analysis relies on simple and intuitive observations about OMP and matrices which satisfy the RIP. For restricted classes of K-sparse signals (those that are highly compressible), a relaxed bound on the isometry constant is also established. A deeper understanding of OMP may benefit the analysis of greedy algorithms in general. To demonstrate this, we also briefly revisit the analysis of the regularized OMP (ROMP) algorithm.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/417d7455d00a481af2f23baf3ad57ad0106899ca

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

Robust High Dimensional Sparse Regression and Matching Pursuit (2013, background): “…property exploited in high-dimensional regression, is that the regressor is often sparse, or near sparse, and as much recent research has demonstrated, in many cases it can be efﬁciently recovered, despite the grossly underdetermined nature of the problem (e.g., [8], [6], [4], [12], [31]).”
Learning hierarchical sparse features for RGB-(D) object recognition (2014, background): “Davenport and Wakin (2010) sufﬁcient for OMP to uniformly recover any K -sparse signal in K iterations.”
Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit (2015, background): “In particular, note that the matrix X need not satisfy the mutual incoherence [32] or restricted isometry properties [11], as two points in a sub-space could be arbitrarily close to each other.”
Structured Compressed Sensing: From Theory to Applications (2011, background): “Theorem 8 [63]: Let the signal and write .”
Generalized Orthogonal Matching Pursuit (2011, background): “(45) In [7], it is shown that the OMP requiresm = O ( K(2) log(n/K) )”
The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing (2012, methodology): “The RIP al so provides sparse recovery guarantees for other heuristics s uch as Orthogonal Matching Pursuit and variants [15], [16], as well as in the denoising case where the right hand side b”
Image compression with Stochastic Winner-Take-All Auto-Encoder (2017, unknown): “SWTA AE is similar to Orthogonal Matching Pursuit (OMP) [15], a common algorithm for image compression using sparse representations [16].”
Spectral compressive sensing (2013, background): “Revisiting our previous example, OMP can recover a K-sparse representation θ from its measurements y = Υθ if the restricted isometry constant δK+1 < 1 3 √ K [45].”
Advances on Spectrum Sensing for Cognitive Radio Networks: Theory and Applications (2017, background): “• Sparsity assumption • Dynamic behaviours for sparsity level [103][104][105][106] [107][108][109][110] [111][112][113]”