A Caltech Library Service

Simultaneous sparse approximation via greedy pursuit

Tropp, J. A. and Gilbert, A. C. and Strauss, M. J. (2005) Simultaneous sparse approximation via greedy pursuit. In: IEEE International Conference on Acoustic, Speech, and Signal Processing (ICASSP '05), Philadelphia, PA, 18-23 March 2005. Vol.5. IEEE , Piscataway, NJ, V-721. ISBN 0-7803-8874-7.

See Usage Policy.


Use this Persistent URL to link to this item:


A simple sparse approximation problem requests an approximation of a given input signal as a linear combination of T elementary signals drawn from a large, linearly dependent collection. An important generalization is simultaneous sparse approximation. Now one must approximate several input signals at once using different linear combinations of the same T elementary signals. This formulation appears, for example, when analyzing multiple observations of a sparse signal that have been contaminated with noise. A new approach to this problem is presented here: a greedy pursuit algorithm called simultaneous orthogonal matching pursuit. The paper proves that the algorithm calculates simultaneous approximations whose error is within a constant factor of the optimal simultaneous approximation error. This result requires that the collection of elementary signals be weakly correlated, a property that is also known as incoherence. Numerical experiments demonstrate that the algorithm often succeeds, even when the inputs do not meet the hypotheses of the proof.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Tropp, J. A.0000-0003-1024-1791
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. [Posted online: 2005-05-09]
Subject Keywords:approximation theory, greedy algorithms, signal representation, time-frequency analysis
Record Number:CaltechAUTHORS:TROicassp05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9043
Deposited By: Archive Administrator
Deposited On:22 Oct 2007
Last Modified:02 Oct 2019 23:56

Repository Staff Only: item control page