February 12, 2003

Joel A. Tropp,
Institute for Computational Engineering and Sciences (ICES), University of Texas at Austin.

Greed is Good: Algorithmic Results for Sparse Approximation.

 Abstract: This talk presents new results on using a greedy algorithm, Orthogonal Matching Pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries. We shall develop a single sufficient condition under which both OMP and Donoho's Basis Pursuit (BP) paradigm can recover an exactly sparse signal. Then, we shall leverage this theory to show that both OMP and BP can recover all exactly sparse signals from a wide class of dictionaries. These quasi-incoherent dictionaries offer a natural generalization of incoherent dictionaries, and the Babel function is introduced to quantify the level of incoherence. Together, these results unify and extend most of the recent work on BP. We shall also discuss the performance of OMP for the general sparse problem over a quasi-incoherent dictionary. For every input signal, OMP can calculate a sparse approximant whose error is only a moderate factor worse than the optimal error which can be attained with the same number of terms. If time permits, we shall also discuss an extension of OMP due to Gilbert, Muthukrishnan, Strauss and Tropp which provides a much better constant of approximation.

Here is a reference.

Time-Frequency Brown Bag Seminar's homepage.