Tight recovery guarantees for orthogonal matching pursuit under Gaussian noise

DOI10.1093/IMAIAI/IAAA021MaRDI QIDQ5155955zbMATH OpenOpenAlexFDO

Authors Chen Amiraz, Robert Krauthgamer, Boaz Nadler

Publication date 13 October 2021

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensinginverse problemsmutual incoherenceorthogonal matching pursuit (OMP)signal reconstructionsparse estimationsupport recovery

Mathematics Subject Classification ID

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

Abstract: Orthogonal Matching pursuit (OMP) is a popular algorithm to estimate an unknown sparse vector from multiple linear measurements of it. Assuming exact sparsity and that the measurements are corrupted by additive Gaussian noise, the success of OMP is often formulated as exactly recovering the support of the sparse vector. Several authors derived a sufficient condition for exact support recovery by OMP with high probability depending on the signal-to-noise ratio, defined as the magnitude of the smallest non-zero coefficient of the vector divided by the noise level. We make two contributions. First, we derive a slightly sharper sufficient condition for two variants of OMP, in which either the sparsity level or the noise level is known. Next, we show that this sharper sufficient condition is tight, in the following sense: for a wide range of problem parameters, there exist a dictionary of linear measurements and a sparse vector with a signal-to-noise ratio slightly below that of the sufficient condition, for which with high probability OMP fails to recover its support. Finally, we present simulations which illustrate that our condition is tight for a much broader range of dictionaries.

Recommendations

• Sparse signals recovery from noisy measurements by orthogonal matching pursuit
• Nonuniform support recovery from noisy random measurements by orthogonal matching pursuit
• Sparsity and incoherence in orthogonal matching pursuit
• A sufficient condition for sparse signals' exact recovery by using OMP algorithm
• Robustness of orthogonal matching pursuit under restricted isometry property

Cited in

(10)

• A performance guarantee for orthogonal matching pursuit using mutual coherence
• Sparse signals recovery from noisy measurements by orthogonal matching pursuit
• Preconditioning for orthogonal matching pursuit with noisy and random measurements: the Gaussian case
• When does OMP achieve exact recovery with continuous dictionaries?
• On sparse recovery algorithms in unions of orthonormal bases
• Variable selection in high-dimension with random designs and orthogonal matching pursuit
• On the Noise Robustness of Simultaneous Orthogonal Matching Pursuit
• A Sharp Condition for Exact Support Recovery With Orthogonal Matching Pursuit
• The recovery guarantee for orthogonal matching pursuit method to reconstruct sparse polynomials
• Support recovery from noisy measurement via orthogonal multi-matching pursuit

This page was built for publication: Tight recovery guarantees for orthogonal matching pursuit under Gaussian noise

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