Perturbation Analysis of Orthogonal Matching Pursuit

DOI10.1109/TSP.2012.2222377MaRDI QIDQ4578364zbMATH OpenOpenAlexFDO

Authors Jie Ding, Laming Chen, Y. T. Gu

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have mainly considered the exact recovery of a sparse signal $$ through $$ and $$, where $$ is a matrix with more columns than rows. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means both $$ and $$ are perturbed. Though exact recovery of an almost sparse signal $$ is no longer feasible, the main contribution reveals that the exact recovery of the locations of $k$ largest magnitude entries of $$ can be guaranteed under reasonable conditions. The error between $$ and solution of OMP is also estimated. It is also demonstrated that the sufficient condition is rather tight by constructing an example. When $$ is strong-decaying, it is proved that the sufficient conditions can be relaxed, and the locations can even be recovered in the order of the entries' magnitude.

Cited in

(14)

• Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms
• Support recovery of greedy block coordinate descent using the near orthogonality property
• Perturbation Analysis of Orthogonal Least Squares
• An improved theoretical analysis of convolutional sparse coding using stripe coherence
• A perturbation analysis based on group sparse representation with orthogonal matching pursuit
• Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
• The stable reconstruction of strongly-decaying block sparse signals
• Analysis of orthogonal multi-matching pursuit under restricted isometry property
• Generalized Orthogonal Matching Pursuit
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• Theoretical analysis of GOMP based on RIP and ROC
• scientific article; zbMATH DE number 6129696 (Why is no real title available?)
• Perturbation analysis of \(L_{1-2}\) method for robust sparse recovery
• Noise folding in completely perturbed compressed sensing

This page was built for publication: Perturbation Analysis of Orthogonal Matching Pursuit

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