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

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

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

(52)

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

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)