Recovery of Sparse Signals via Generalized Orthogonal Matching Pursuit: A New Analysis

DOI10.1109/TSP.2015.2498132MaRDI QIDQ4618210zbMATH OpenOpenAlexFDO

Authors Jian Wang, Suhyuk Kwon, Ping Li, Byonghyo Shim

Publication date 7 February 2019

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

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

Mathematics Subject Classification ID

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

Abstract: As an extension of orthogonal matching pursuit (OMP) improving the recovery performance of sparse signals, generalized OMP (gOMP) has recently been studied in the literature. In this paper, we present a new analysis of the gOMP algorithm using restricted isometry property (RIP). We show that if the measurement matrix $mathbfPhiinmathcal{R}^{mimesn}$ satisfies the RIP with ${\displaystyle }$delta_{max left{9, S + 1 ight}K} leq frac{1}{8},${\displaystyle }$ then gOMP performs stable reconstruction of all $K$-sparse signals $mathbfxinmathcal{R}^n$ from the noisy measurements $mathbfy=mathbfPhix+mathbfv$ within $maxleftK,leftlfloorfrac8KSightflooright$ iterations where $mathbfv$ is the noise vector and $S$ is the number of indices chosen in each iteration of the gOMP algorithm. For Gaussian random measurements, our results indicate that the number of required measurements is essentially $m=mathcalO(KlogfracnK)$, which is a significant improvement over the existing result $m=mathcalO(K^{2}logfracnK)$, especially for large $K$.

Cited in

(13)

• Probabilistic matching pursuit with Gabor dictionaries.
• A new sufficient condition for sparse recovery with multiple orthogonal least squares
• A perturbation analysis based on group sparse representation with orthogonal matching pursuit
• A reweighted symmetric smoothed function approximating L₀-norm regularized sparse reconstruction method
• Compressed sensing construction for underdetermined source separation
• Conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery
• An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit
• Generalized Orthogonal Matching Pursuit
• Perturbation Analysis of Orthogonal Least Squares
• Sparse recovery with general frame via general-dual-based analysis Dantzig selector
• Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms
• Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise
• Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares

This page was built for publication: Recovery of Sparse Signals via Generalized Orthogonal Matching Pursuit: A New Analysis

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