Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property

DOI10.1109/TIT.2010.2054653MaRDI QIDQ5281300zbMATH OpenFDO

Authors Mark A. Davenport, Michael B. Wakin

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.0083

Mathematics Subject Classification ID

Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: 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 $delta<frac13sqrtK$) is sufficient for OMP to exactly recover any $K$-sparse signal. Our 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.

Cited in

(56)

• Automatic modulation recognition using compressive cyclic features
• Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
• A remark on joint sparse recovery with OMP algorithm under restricted isometry property
• Dictionary evaluation and optimization for sparse coding based speech processing
• Sparse polynomial chaos expansions via compressed sensing and D-optimal design
• A sharp RIP condition for orthogonal matching pursuit
• A rolling bearing fault detection method based on compressed sensing and a neural network
• Adaboost-based ensemble of polynomial chaos expansion with adaptive sampling
• Robust sparse recovery via a novel convex model
• Search for sparse solutions of super-large systems with a tensor structure
• Greedy orthogonal matching pursuit for subspace clustering to improve graph connectivity
• Fast overcomplete dictionary construction with probabilistic guarantees
• Spectral compressive sensing
• Sparse signals recovery from noisy measurements by orthogonal matching pursuit
• On rank awareness, thresholding, and MUSIC for joint sparse recovery
• Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
• Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems
• Alternating direction method of multipliers for solving dictionary learning models
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields
• Stability and robustness of weak orthogonal matching pursuits
• Off-grid DOA estimation via real-valued sparse Bayesian method in compressed sensing
• Design of wideband fractional-order differentiator using interlaced sampling method
• Sparse approximation is provably hard under coherent dictionaries
• Cosparsity in Compressed Sensing
• Compressive sensing of analog signals using discrete prolate spheroidal sequences
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• The restricted isometry property for random block diagonal matrices
• On collaborative compressive sensing systems: the framework, design, and algorithm
• Compressed classification learning with Markov chain samples
• Robustness of orthogonal matching pursuit under restricted isometry property
• Analysis of orthogonal multi-matching pursuit under restricted isometry property
• Binary sparse signal recovery with binary matching pursuit
• Sparsity-Based MIMO Radars
• scientific article; zbMATH DE number 7572477 (Why is no real title available?)
• Sparse probability assessment heuristic based on orthogonal matching pursuit
• scientific article; zbMATH DE number 7307477 (Why is no real title available?)
• Quasi-linear compressed sensing
• A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
• Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms
• Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression)
• A new result on recovery sparse signals using orthogonal matching pursuit
• Heuristics for Finding Sparse Solutions of Linear Inequalities
• Sparse signal reconstruction via collaborative neurodynamic optimization
• Classifier-based adaptive polynomial chaos expansion for high-dimensional uncertainty quantification
• Some results on OMP algorithm for MMV problem
• Error estimates for orthogonal matching pursuit and random dictionaries
• Phase transitions for greedy sparse approximation algorithms
• Towards probabilistic robust and sparsity-free compressive sampling in civil engineering: a review
• The stable reconstruction of strongly-decaying block sparse signals
• Dynamic thresholding algorithm with memory for linear inverse problems
• Noise folding in completely perturbed compressed sensing
• Sparse recovery of decaying signals by the piecewise generalized orthogonal matching pursuit algorithm
• Recovery conditions for generalized orthogonal matching pursuit based coherence
• Randomized orthogonal matching pursuit algorithm with adaptive partial selection for sparse signal recovery
• A new recovery analysis of block orthogonal greedy algorithm

This page was built for publication: Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281300)