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.

Date Published: 17 September 2005
PDF: 11 pages
Proc. SPIE 5914, Wavelets XI, 591412 (17 September 2005); doi: 10.1117/12.618154

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