Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property

DOI10.1109/TIT.2010.2054653zbMATH Open1366.94093arXiv0909.0083MaRDI QIDQ5281300FDOQ5281300

Authors: Mark A. Davenport, Michael B. Wakin 

Publication date: 27 July 2017

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

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.

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)

Cited In (52)

• Search for sparse solutions of super-large systems with a tensor structure
• Title not available (Why is that?)
• Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems
• A remark on joint sparse recovery with OMP algorithm under restricted isometry property
• Error estimates for orthogonal matching pursuit and random dictionaries
• 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
• Title not available (Why is that?)
• Analysis of orthogonal multi-matching pursuit under restricted isometry property
• Robustness of orthogonal matching pursuit under restricted isometry property
• Heuristics for Finding Sparse Solutions of Linear Inequalities
• Alternating direction method of multipliers for solving dictionary learning models
• Greedy orthogonal matching pursuit for subspace clustering to improve graph connectivity
• Compressive sensing of analog signals using discrete prolate spheroidal sequences
• Sparse polynomial chaos expansions via compressed sensing and D-optimal design
• Sparse signal reconstruction via collaborative neurodynamic optimization
• Off-grid DOA estimation via real-valued sparse Bayesian method in compressed sensing
• Design of wideband fractional-order differentiator using interlaced sampling method
• 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 Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
• A rolling bearing fault detection method based on compressed sensing and a neural network
• On rank awareness, thresholding, and MUSIC for joint sparse recovery
• Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression)
• Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
• Sparse approximation is provably hard under coherent dictionaries
• 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
• Noise folding in completely perturbed compressed sensing
• Classifier-based adaptive polynomial chaos expansion for high-dimensional uncertainty quantification
• A sharp RIP condition for orthogonal matching pursuit
• Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms
• The stable reconstruction of strongly-decaying block sparse signals
• Dynamic thresholding algorithm with memory for linear inverse problems
• Towards probabilistic robust and sparsity-free compressive sampling in civil engineering: a review

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)