期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 56, 期 9, 页码 4395-4401出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2010.2054653
关键词
Compressive sensing; greedy algorithms; orthogonal matching pursuit (OMP); redundant dictionaries; restricted isometry property (RIP); sparse approximation
资金
- NSF [CCF-0830320]
- DARPA [N66001-08-1-2065, HR0011-08-1-0078]
- AFOSR [FA9550-07-1-0301, FA9550-09-1-0465]
- ONR [N00014-07-1-0936]
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 < 1/3 root 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据