Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise

By Tommaso Cai, Lie Wang. IEEE Transactions on Information Theory, 2011

1,244 citations recorded by the source corpus.

We consider the orthogonal matching pursuit (OMP) algorithm for the recovery of a high-dimensional sparse signal based on a small number of noisy linear measurements. OMP is an iterative greedy algorithm that selects at each step the column, which is most correlated with the current residuals. In this paper, we present a fully data driven OMP algorithm with explicit stopping rules. It is shown that under conditions on the mutual incoherence and the minimum magnitude of the nonzero components of the signal, the support of the signal can be recovered exactly by the OMP algorithm with high probability. In addition, we also consider the problem of identifying significant components in the case where some of the nonzero components are possibly small. It is shown that in this case the OMP algorithm will still select all the significant components before possibly selecting incorrect ones. Moreover, with modified stopping rules, the OMP algorithm can ensure that no zero components are selected.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/653c702bdc9403151cad521cefa14ee3eaf3d320

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

1. Nuria González-Prelcic
2. Athina P. Petropulu
3. Robert W. Heath
4. V. Poor
5. Shunqiao Sun

In Computational Mechanics

1. Nuria González-Prelcic
2. Roi Méndez-Rial
3. Vidya Muthukumar
4. Ahmed Alkhateeb
5. Athina P. Petropulu
6. Anant Sahai
7. Robert W. Heath
8. V. Poor

In Signal Processing

1. Nuria González-Prelcic
2. Ahmed Alkhateeb
3. Athina P. Petropulu
4. Robert W. Heath
5. V. Poor
6. Shunqiao Sun
7. Thomas Strohmer
8. Götz E. Pfander

Citations in the corpus

• Harmless interpolation of noisy data in regression (2019, background): “For the latter, our error bound derives from a much stronger variable selection guarantee [31] which implicitly requires the SNR to scale as log d.”
• MIMO Radar for Advanced Driver-Assistance Systems and Autonomous Driving: Advantages and Challenges (2020, methodology): “or greedy methods, such as orthogonal matching pursuit (OMP) [77].”
• Hybrid MIMO Architectures for Millimeter Wave Communications: Phase Shifters or Switches? (2015, background): “The OMP recovery guarantees in the presence of noise were considered in [78].”