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

Rémi Gribonval, Morten Nielsen

Research output: Book/ReportReportResearch

Abstract

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.
Original languageEnglish
Place of PublicationInstitut de Recherche en Informatique et Systèmes Alèatoires, Rennes
PublisherFrance
Number of pages19
Publication statusPublished - 2005
SeriesPublication interne
Number1684
ISSN1166-8687

Keywords

  • Sparse representation
  • Overcomplete dictionary
  • Linear programming
  • Independent component analysis

Fingerprint

Dive into the research topics of 'Beyond sparsity: recovering structured representations by l¹ minimization and greedy algorithms. - Application to the analysis of sparse underdetermined ICA -'. Together they form a unique fingerprint.

Cite this