This paper presents a new analysis for the orthogonal matching pursuit (OMP) algorithm. It is shown that if the restricted isometry property (RIP) is satisfied at sparsity level $O(\bar{ k})$, then OMP can recover a $\bar{ k}$-sparse signal in 2-norm. For compressed sensing applications, this result implies that in order to uniformly recover a $\bar{ k}$-sparse signal in $\Real^d$, only $O(\bar{ k} \ln d)$ random projections are needed. This analysis improves earlier results on OMP that depend on stronger conditions such as mutual incoherence that can only be satisfied with $\Omega(\bar{ k}^2 \ln d)$ random projections.
Categories: cs.IT math.IT