Authors’ 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 J. A. Tropp, A. C. Gilbert and M. J. Strauss [Signal Process. 86, No. 3, 572–588 (2006; Zbl 1163.94396)]. The paper first provides 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.
The authors unlock the situation by performing an \(average\) case analysis of both algorithms. First, they set up a general probabilistic signal model in which the coefficients of the atoms are drawn at random from the standard Gaussian distribution. Second, they 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, the authors analyse the influence of selecting the set of correct atoms at random. They show that, if the dictionary satisfies a uniform uncertainty principle [E. Candes and T. Tao, IEEE Trans. Inf. Theory 52, No. 12, 5406–5425 (2006; doi:10.1109/TIT.2006.885507)], the probability that simultaneous OMP fails to recover any sufficiently sparse set of atoms gets increasingly smaller as the number of channels increases.