CaltechAUTHORS
  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-V-724. ISBN 0-7803-8874-7 http://resolver.caltech.edu/CaltechAUTHORS:TROicassp05

[img]
Preview
PDF
See Usage Policy.

285Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:TROicassp05

Abstract

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
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:http://resolver.caltech.edu/CaltechAUTHORS:TROicassp05
Alternative URL:http://dx.doi.org/10.1109/ICASSP.2005.1416405
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9043
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:22 Oct 2007
Last Modified:26 Dec 2012 09:44

Repository Staff Only: item control page