Skip to Main content Skip to Navigation
Reports

Local stability and robustness of sparse dictionary learning in the presence of noise

Rodolphe Jenatton 1, * Rémi Gribonval 2 Francis Bach 3, 4
* Corresponding author
2 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
4 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : A popular approach within the signal processing and machine learning communities consists in modelling signals as sparse linear combinations of atoms selected from a learned dictionary. While this paradigm has led to numerous empirical successes in various fields ranging from image to audio processing, there have only been a few theoretical arguments supporting these evidences. In particular, sparse coding, or sparse dictionary learning, relies on a non-convex procedure whose local minima have not been fully analyzed yet. In this paper, we consider a probabilistic model of sparse signals, and show that, with high probability, sparse coding admits a local minimum around the reference dictionary generating the signals. Our study takes into account the case of over-complete dictionaries and noisy signals, thus extending previous work limited to noiseless settings and/or under-complete dictionaries. The analysis we conduct is non-asymptotic and makes it possible to understand how the key quantities of the problem, such as the coherence or the level of noise, can scale with respect to the dimension of the signals, the number of atoms, the sparsity and the number of observations.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/hal-00737152
Contributor : Rodolphe Jenatton <>
Submitted on : Monday, October 1, 2012 - 12:58:32 PM
Last modification on : Friday, July 2, 2021 - 3:37:40 AM
Long-term archiving on: : Wednesday, January 2, 2013 - 5:35:08 AM

Files

localDL_HAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00737152, version 1
  • ARXIV : 1210.0685

Citation

Rodolphe Jenatton, Rémi Gribonval, Francis Bach. Local stability and robustness of sparse dictionary learning in the presence of noise. [Research Report] 2012, pp.41. ⟨hal-00737152⟩

Share

Metrics

Record views

2115

Files downloads

1221