Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property

TLDR

Orthogonal matching pursuit (OMP) is the canonical greedy algorithm for sparse approximation, and a deeper understanding of OMP may benefit the analysis of greedy algorithms in general. The paper demonstrates that the restricted isometry property (RIP) can be used for a straightforward analysis of OMP. The analysis relies on simple and intuitive observations about OMP and matrices which satisfy the RIP, and the authors also briefly revisit the analysis of the regularized OMP (ROMP) algorithm. The authors conclude that the RIP of order K+1 with isometry constant δ < 1/(3√K) suffices for OMP to exactly recover any K‑sparse signal, and for highly compressible K‑sparse signals a relaxed bound on the isometry constant is also established.

Abstract

Orthogonal matching pursuit (OMP) is the canonical greedy algorithm for sparse approximation. In this paper we demonstrate that the restricted isometry property (RIP) can be used for a very straightforward analysis of OMP. Our main conclusion is that the RIP of order K+1 (with isometry constant δ <; [ 1/( 3√K)]) is sufficient for OMP to exactly recover any K-sparse signal. The analysis relies on simple and intuitive observations about OMP and matrices which satisfy the RIP. For restricted classes of K-sparse signals (those that are highly compressible), a relaxed bound on the isometry constant is also established. A deeper understanding of OMP may benefit the analysis of greedy algorithms in general. To demonstrate this, we also briefly revisit the analysis of the regularized OMP (ROMP) algorithm.