Share Email Print

Proceedings Paper

Average-case analysis of greedy pursuit
Author(s): Joel A. Tropp
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 17 September 2005
PDF: 11 pages
Proc. SPIE 5914, Wavelets XI, 591412 (17 September 2005); doi: 10.1117/12.618154
Show Author Affiliations
Joel A. Tropp, The Univ. of Michigan (United States)

Published in SPIE Proceedings Vol. 5914:
Wavelets XI
Manos Papadakis; Andrew F. Laine; Michael A. Unser, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?