Nonuniform support recovery from noisy random measurements by Orthogonal Matching Pursuit

This article considers nonuniform support recovery via Orthogonal Matching Pursuit (OMP) from noisy random measurements. Given mm admissible random measurements (of which Subgaussian measurements is a special case) of a fixed ss-sparse signal xx in RnRn corrupted with additive noise, we show that under a condition on the minimum magnitude of the nonzero components of xx, OMP can recover the support of xx exactly after ss iterations with overwhelming probability provided that m=O(slogn)m=O(slogn). This extends the results of Tropp and Gilbert (2007) [53] to the case with noise. It is a real improvement over previous results in the noisy case, which are based on mutual incoherence property or restricted isometry property analysis and require O(s2logn)O(s2logn) random measurements. In addition, this article also considers sparse recovery from noisy random frequency measurements via OMP. Similar results can be obtained for the partial random Fourier matrix via OMP provided that m=O(s(s+log(n−s)))m=O(s(s+log(n−s))). Thus, for some special cases, this answers the open question raised by Kunis and Rauhut (2008) [34], and Tropp and Gilbert (2007) [53].