53 articles  [english version]

inria-00369562, version 1

Basis Identification from Random Sparse Samples

Rémi Gribonval () a, 1, Karin Schnass 2

SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations (2009)

Résumé : This article treats the problem of learning a dictionary providing sparse representations for a given signal class, via ℓ1-minimisation. The problem is to identify a dictionary [\Phi] from a set of training samples Y knowing that [Y = \PhiX] for some coefficient matrix X. Using a characterisation of coefficient matrices X that allow to recover any basis as a local minimum of an ℓ1-minimisation problem, it is shown that certain types of sparse random coefficient matrices will ensure local identifiability of the basis with high probability. The typically sufficient number of training samples grows up to a logarithmic factor linearly with the signal dimension.

  • a –  INRIA
  • 1 :  METISS (INRIA - IRISA)
  • CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
  • 2 :  LTS2 - EPFL
  • École Polytechnique Fédérale de Lausanne
  • Domaine : Informatique/Traitement du signal et de l'image
    Sciences de l'ingénieur/Traitement du signal et de l'image
 
  • inria-00369562, version 1
  • http://hal.inria.fr/inria-00369562
  • oai:hal.inria.fr:inria-00369562
  • Contributeur : Ist Rennes <>
  • Soumis le : Mardi 24 Mars 2009, 11:25:57
  • Dernière modification le : Mardi 24 Mars 2009, 11:50:05