Math @ Duke

Publications [#303203] of Robert Calderbank
Papers Published
 Chi, Y; Calderbank, R, CoherenceBased Performance Guarantees of Orthogonal Matching Pursuit
(September, 2012) [1209.6267v1]
(last updated on 2017/12/11)
Abstract: In this paper, we present coherencebased performance guarantees of
Orthogonal Matching Pursuit (OMP) for both support recovery and signal
reconstruction of sparse signals when the measurements are corrupted by noise.
In particular, two variants of OMP either with known sparsity level or with a
stopping rule are analyzed. It is shown that if the measurement matrix
$X\in\mathbb{C}^{n\times p}$ satisfies the strong coherence property, then with
$n\gtrsim\mathcal{O}(k\log p)$, OMP will recover a $k$sparse signal with high
probability. In particular, the performance guarantees obtained here separate
the properties required of the measurement matrix from the properties required
of the signal, which depends critically on the minimum signal to noise ratio
rather than the power profiles of the signal. We also provide performance
guarantees for partial support recovery. Comparisons are given with other
performance guarantees for OMP using worstcase analysis and the sorted one
step thresholding algorithm.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

