Orthogonal Matching Pursuit for Sparse Signal Recovery with Noise
Tony Cai and Lie Wang
-
Abstract:
We consider the orthogonal matching pursuit (OMP) algorithm for the
recovery of a high-dimensional sparse signal based on a small number of
noisy measurements. The OMP is an iterative greedy algorithm that selects
at each step the variable which is most correlated with the current
residuals. Stopping rules are given and the algorithm is fully data driven.
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 variables
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 variables before possibly
selecting incorrect ones. Moreover, with modified stopping rules,
the OMP algorithm can ensure that no incorrect variables are selected.
- Paper:
pdf file.
- Other related papers:
Cai, T., Wang, L. & Xu, G. (2010).
Shifting inequality and recovery of sparse signals.
IEEE Transactions on Signal Processing 58, 1300-1308.Cai, T., Wang, L. & Xu, G. (2010).
New bounds for restricted isometry constants.
IEEE Transactions on Information Theory 56, 4388-4394.Cai, T., Wang, L. & Xu, G. (2010).
Stable recovery of sparse signals and an oracle inequality.
IEEE Transactions on Information Theory 56, 3516-3522.Cai, T., Xu, G. & Zhang, J. (2009).
On recovery of sparse signals via l1 minimization.
IEEE Transactions on Information Theory 55 , 3388-3397.