Analysis of Orthogonal Matching Pursuit using the Restricted Isometry Property

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 delta is greater than 1/square root of 3/K) is sufficient for OMP to exactly recover any K-sparse signal. Our 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 2009
Accession Number
ADA521441

Entities

People

  • Mark A. Davenport
  • Michael B. Wakin

Organizations

  • Rice University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Compressed Sensing
  • Electrical Engineering
  • Electronic Mail
  • Engineering
  • Guarantees
  • Information Operations
  • Iterations
  • Measurement
  • Observation
  • Probability
  • Random Variables
  • Recovery
  • Residuals

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Battery Technology and Engineering