HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms

Rémi Gribonval 1 Holger Rauhut 2 Karin Schnass 3 Pierre Vandergheynst 3
1 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : 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 in [28]. 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 [5], the probability that simultaneous OMP fails to recover any sufficiently sparse set of atoms gets increasingly smaller as the number of channels increases. To conclude, we study the robustness of these algorithms to an imperfect knowledge of the dictionary, a situation met in sparsity-based blind source separation where the dictionary, which corresponds to a mixing matrix, is only approximately known. In this framework, we estimate the probability of failure of the considered algorithms as a function of the similarity between the reference dictionary and the approximate one, which we measure with the smallest correlation between corresponding pairs of atoms.
Document type :
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download

Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Tuesday, May 15, 2007 - 11:11:34 AM
Last modification on : Friday, February 4, 2022 - 3:22:24 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 11:45:10 PM


Files produced by the author(s)


  • HAL Id : inria-00146660, version 1


Rémi Gribonval, Holger Rauhut, Karin Schnass, Pierre Vandergheynst. Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms. [Research Report] PI 1848, 2007, pp.34. ⟨inria-00146660⟩



Record views


Files downloads