Average-case analysis of greedy pursuit

Joel A. Tropp

doi:10.1117/12.618154

17 September 2005 Average-case analysis of greedy pursuit

Joel A. Tropp

Proceedings Volume 5914, Wavelets XI; 591412 (2005) https://doi.org/10.1117/12.618154
Event: Optics and Photonics 2005, 2005, San Diego, California, United States

Abstract

Recent work on sparse approximation has focused on the theoretical performance of algorithms for random inputs. This average-case behavior is typically far better than the behavior for the worst inputs. Moreover, an average-case analysis fits naturally with the type of signals that arise in certain applications, such as wireless communications. This paper describes what is currently known about the performance of greedy prusuit algorithms with random inputs. In particular, it gives a new result for the performance of Orthogonal Matching Pursuit (OMP) for sparse signals contaminated with random noise, and it explains recent work on recovering sparse signals from random measurements via OMP. The paper also provides a list of open problems to stimulate further research.

Citation Download Citation

Joel A. Tropp "Average-case analysis of greedy pursuit", Proc. SPIE 5914, Wavelets XI, 591412 (17 September 2005); https://doi.org/10.1117/12.618154

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available