A Sharp Condition for Exact Support Recovery With Orthogonal Matching Pursuit

DOI10.1109/TSP.2016.2634550MaRDI QIDQ4620663zbMATH OpenFDO

Authors Jinming Wen, Zhengchun Zhou, Jian Wang, Xiaohu Tang, Qun Mo

Publication date 8 February 2019

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

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

Mathematics Subject Classification ID

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

Abstract: Support recovery of sparse signals from noisy measurements with orthogonal matching pursuit (OMP) has been extensively studied. In this paper, we show that for any $K$-sparse signal $x$, if a sensing matrix $A$ satisfies the restricted isometry property (RIP) with restricted isometry constant (RIC) $delt{a}_{K+1}<1/sqrtK+1$, then under some constraints on the minimum magnitude of nonzero elements of $x$, OMP exactly recovers the support of $x$ from its measurements $y=Ax+v$ in $K$ iterations, where $v$ is a noise vector that is $el{l}_2$ or $el{l}_{infty}$ bounded. This sufficient condition is sharp in terms of $delt{a}_{K+1}$ since for any given positive integer $K$ and any $1/sqrtK+1leqdelta<1$, there always exists a matrix $A$ satisfying the RIP with $delt{a}_{K+1}=delta$ for which OMP fails to recover a $K$-sparse signal $x$ in $K$ iterations. Also, our constraints on the minimum magnitude of nonzero elements of $x$ are weaker than existing ones. Moreover, we propose worst-case necessary conditions for the exact support recovery of $x$, characterized by the minimum magnitude of the nonzero elements of $x$.

Recommendations

• Some New Results About Sufficient Conditions for Exact Support Recovery of Sparse Signals via Orthogonal Matching Pursuit
• The exact recovery of sparse signals via orthogonal matching pursuit
• A sharp RIP condition for orthogonal matching pursuit
• Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
• Support Recovery With Orthogonal Matching Pursuit in the Presence of Noise
• A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit
• Nearly Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
• Tight recovery guarantees for orthogonal matching pursuit under Gaussian noise
• Exact Recovery Conditions for Sparse Representations With Partial Support Information
• On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit

Cited in

(27)

• Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
• Sparsity and incoherence in orthogonal matching pursuit
• Nonuniform support recovery from noisy random measurements by orthogonal matching pursuit
• Unconstrained \(\ell_1\)-\(\ell_2\) minimization for sparse recovery via mutual coherence
• Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
• A reweighted symmetric smoothed function approximating L₀-norm regularized sparse reconstruction method
• Binary sparse signal recovery with binary matching pursuit
• scientific article; zbMATH DE number 7572477 (Why is no real title available?)
• Performance analysis for unconstrained analysis based approaches
• Perturbation Analysis of Orthogonal Least Squares
• A survey on compressive sensing: classical results and recent advancements
• A new result on recovery sparse signals using orthogonal matching pursuit
• Codes for exact support recovery of sparse vectors from inaccurate linear measurements and their decoding
• Binary generalized orthogonal matching pursuit
• Nonoverlapping convex polytopes with vertices in a Boolean cube and other problems in coding theory
• Some results on OMP algorithm for MMV problem
• Theoretical analysis of GOMP based on RIP and ROC
• Non-negative sparse recovery via momentum-boosted adaptive thresholding algorithm
• Group projected subspace pursuit for block sparse signal reconstruction: convergence analysis and applications
• Theory and fast learned solver for ^1-TV regularization
• Tensor recovery from quantized measurements based on modewise operators
• Heavy-ball enhanced pseudo-inverse-based hard thresholding algorithms for sparse linear inverse problems
• An improved theoretical analysis of convolutional sparse coding using stripe coherence
• Randomized orthogonal matching pursuit algorithm with adaptive partial selection for sparse signal recovery
• On the conjugate gradient subspace pursuit algorithm
• Binary least squares: an algorithm for binary sparse signal recovery
• A new metric for the recoverability of sparse signals

This page was built for publication: A Sharp Condition for Exact Support Recovery With Orthogonal Matching Pursuit

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