000104067 001__ 104067
000104067 005__ 20190316233955.0
000104067 0247_ $$2doi$$a10.1007/s00041-008-9044-y
000104067 02470 $$2DAR$$a13577
000104067 02470 $$2ISI$$a000261411300004
000104067 037__ $$aARTICLE
000104067 245__ $$aAtoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
000104067 269__ $$a2008
000104067 260__ $$c2008
000104067 336__ $$aJournal Articles
000104067 520__ $$aThis 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.
000104067 6531_ $$aITS
000104067 6531_ $$aLTS2
000104067 6531_ $$aaverage analysis
000104067 6531_ $$aOMP
000104067 6531_ $$aThresholding
000104067 6531_ $$amulti-channel
000104067 700__ $$aGribonval, Remi
000104067 700__ $$aRauhut, Holger
000104067 700__ $$0240457$$g168927$$aSchnass, Karin
000104067 700__ $$g120906$$aVandergheynst, Pierre$$0240428
000104067 773__ $$j14$$tJournal of Fourier Analysis and Applications$$k5$$q655-687
000104067 8564_ $$zURL
000104067 8564_ $$uhttps://infoscience.epfl.ch/record/104067/files/AverageGreed.pdf$$zn/a$$s303956
000104067 909C0 $$xU10380$$0252392$$pLTS2
000104067 909CO $$ooai:infoscience.epfl.ch:104067$$qGLOBAL_SET$$pSTI$$particle
000104067 937__ $$aEPFL-ARTICLE-104067
000104067 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000104067 980__ $$aARTICLE