Beyond sparsity: recovering structured representations by l¹ minimization and greedy algorithms. - Application to the analysis of sparse underdetermined ICA -

In a series of recent results, several authors have shown that both l¹-minimization (Basis Pursuit) and greedy algorithms (Matching Pursuit) 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 more general identifiable structures that support signals that can be recovered exactly by l¹ minimization and greedy algorithms. In addition, we obtain that if the output of an arbitrary decompostiion 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 $X=\mathbf{A} S \Phi^T)$ often used in, e.g. under-determined source separation problems or in multichannel signal processing.