104067
20190316233955.0
doi
10.1007/s00041-008-9044-y
DAR
13577
ISI
000261411300004
ARTICLE
Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
2008
2008
Journal Articles
This paper provides new results on computing simultaneous sparse approximations of multichannel signals over redundant dictionaries using two greedy algorithms. The first one, p-thresholding, selects the S atoms that have the largest $p$-correlation while the second one, p-simultaneous matching pursuit (p-SOMP), is a generalisation of an algorithm studied by Tropp. We first provide exact recovery conditions as well as worst case analyses of all algorithms. The results, expressed using the standard cumulative coherence, are very reminiscent of the single channel case and, in particular, impose stringent restrictions on the dictionary. We unlock the situation by performing an average case analysis of both algorithms. First, we set up a general probabilistic signal model in which the coefficients of the atoms are drawn at random from the standard gaussian distribution. Second, we show that under this model, and with mild conditions on the coherence, the probability that p-thresholding and p-SOMP fail to recover the correct components is overwhelmingly small and gets smaller as the number of channels increases. Furthermore, we analyse the influence of selecting the set of correct atoms at random. We show that, if the dictionary satisfies a uniform uncertainty principle, the probability that simultaneous OMP fails to recover any sufficiently sparse set of atoms gets increasingly smaller as the number of channels increases.
ITS
LTS2
average analysis
OMP
Thresholding
multi-channel
Gribonval, Remi
Rauhut, Holger
240457
Schnass, Karin
168927
240428
Vandergheynst, Pierre
120906
14
5
655-687
Journal of Fourier Analysis and Applications
URL
303956
http://infoscience.epfl.ch/record/104067/files/AverageGreed.pdf
n/a
252392
LTS2
U10380
oai:infoscience.epfl.ch:104067
STI
article
GLOBAL_SET
EPFL-ARTICLE-104067
EPFL
REVIEWED
PUBLISHED
ARTICLE