Beyond sparsity: Recovering structured representations by ${\ell}^1$ minimization and greedy algorithms |
| |
Authors: | Rémi?Gribonval Morten?Nielsen |
| |
Institution: | (1) IRISA-INRIA, Campus de Beaulieu, F-35042 Rennes Cedex, France;(2) Department of Mathematical Sciences, Aalborg University, Fredrik Bajers Vej 7 G, DK-9220 Aalborg East, Denmark |
| |
Abstract: | Finding a sparse approximation of a signal from an arbitrary dictionary is a very useful tool to solve many problems in signal
processing. Several algorithms, such as Basis Pursuit (BP) and Matching Pursuits (MP, also known as greedy algorithms), have
been introduced to compute sparse approximations of signals, but such algorithms a priori only provide sub-optimal solutions. In general, it is difficult to estimate how close a computed solution is from the optimal
one. In a series of recent results, several authors have shown that both BP and MP can successfully recover a sparse representation
of a signal provided that it is sparse enough, that is to say if its support (which indicates where are located the nonzero
coefficients) is of sufficiently small size. In this paper we define identifiable structures that support signals that can
be recovered exactly by minimization (Basis Pursuit) and greedy algorithms. In other words, if the support of a representation belongs to an identifiable
structure, then the representation will be recovered by BP and MP. In addition, we obtain that if the output of an arbitrary
decomposition algorithm is supported on an identifiable structure, then one can be sure that the representation is optimal
within the class of signals supported by the structure. As an application of the theoretical results, we give a detailed study
of a family of multichannel dictionaries with a special structure (corresponding to the representation problem ) often used in, e.g., under-determined source sepa-ration problems or in multichannel signal processing. An identifiable
structure for such dictionaries is defined using a generalization of Tropp’s Babel function which combines the coherence of
the mixing matrix with that of the time-domain dictionary , and we obtain explicit structure conditions which ensure that both minimization and a multi-channel variant of Matching Pursuit can recover structured multichannel representations. The multichannel
Matching Pursuit algorithm is described in detail and we conclude with a discussion of some implications of our results in
terms of blind source separation based on sparse decompositions.
Communicated by Yuesheng Xu |
| |
Keywords: | sparse approximations greedy algorithm -minimization" target="_blank">gif" alt="$\ell^1$" align="middle" border="0">-minimization basis pursuit algorithm linear programming multichannel representations sparse component analysis |
本文献已被 SpringerLink 等数据库收录! |
|