DocumentCode :
2950035
Title :
Simultaneous sparse approximation via greedy pursuit
Author :
Tropp, A. ; Gilbert, A.C. ; Strauss, M.J.
Author_Institution :
Dept. of Math., Michigan Univ., Ann Arbor, MI, USA
Volume :
5
fYear :
2005
fDate :
18-23 March 2005
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.
Keywords :
approximation theory; greedy algorithms; signal representation; time-frequency analysis; elementary signal linear combination; greedy pursuit algorithm; signal incoherence; simultaneous orthogonal matching pursuit; simultaneous sparse approximation; weakly correlated elementary signals; Approximation algorithms; Approximation error; Dictionaries; Matching pursuit algorithms; Mathematics; Optimized production technology; Pursuit algorithms; Signal analysis; Sparse matrices; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on
ISSN :
1520-6149
Print_ISBN :
0-7803-8874-7
Type :
conf
DOI :
10.1109/ICASSP.2005.1416405
Filename :
1416405
Link To Document :
بازگشت