TY - RPRT
T1 - Beyond sparsity: recovering structured representations by l¹ minimization and greedy algorithms. - Application to the analysis of sparse underdetermined ICA -
AU - Gribonval, Rémi
AU - Nielsen, Morten
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - Sparse representation
KW - Overcomplete dictionary
KW - Linear programming
KW - Independent component analysis
M3 - Report
T3 - Publication interne
BT - Beyond sparsity: recovering structured representations by l¹ minimization and greedy algorithms. - Application to the analysis of sparse underdetermined ICA -
PB - France
CY - Institut de Recherche en Informatique et Systèmes Alèatoires, Rennes
ER -