An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit

DOI10.1109/TIT.2014.2338314zbMATH Open1360.94052arXiv1401.0578MaRDI QIDQ2986182FDOQ2986182

Authors: Ling-Hua Chang, Jwo-Yuh Wu 

Publication date: 16 May 2017

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

Abstract: A sufficient condition reported very recently for perfect recovery of a K-sparse vector via orthogonal matching pursuit (OMP) in K iterations is that the restricted isometry constant of the sensing matrix satisfies delta_K+1<1/(sqrt(delta_K+1)+1). By exploiting an approximate orthogonality condition characterized via the achievable angles between two orthogonal sparse vectors upon compression, this paper shows that the upper bound on delta can be further relaxed to delta_K+1<(sqrt(1+4*delta_K+1)-1)/(2K).This result thus narrows the gap between the so far best known bound and the ultimate performance guarantee delta_K+1<1/(sqrt(delta_K+1)) that is conjectured by Dai and Milenkovic in 2009. The proposed approximate orthogonality condition is also exploited to derive less restricted sufficient conditions for signal reconstruction in several compressive sensing problems, including signal recovery via OMP in a noisy environment, compressive domain interference cancellation, and support identification via the subspace pursuit algorithm.

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

Recommendations

• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Recovery of sparse signals using OMP and its variants: convergence analysis based on RIP
• A new result on recovery sparse signals using orthogonal matching pursuit
• Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
• On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit
• Recovery of sparse signals by orthogonal multi-matching pursuit
• Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization
• The exact recovery of sparse signals via orthogonal matching pursuit
• Recovery of Sparse Signals via Generalized Orthogonal Matching Pursuit: A New Analysis
• Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise

Mathematics Subject Classification ID

Detection theory in information and communication theory (94A13) Application of orthogonal and other special functions (94A11)

Cited In (5)

• Support recovery of greedy block coordinate descent using the near orthogonality property
• Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
• When does OMP achieve exact recovery with continuous dictionaries?
• Theoretical analysis of GOMP based on RIP and ROC
• Dynamic thresholding algorithm with memory for linear inverse problems

This page was built for publication: An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit

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