Skip to Main content Skip to Navigation
Conference papers

On The Sample Complexity Of Sparse Dictionary Learning

Abstract : In the synthesis model signals are represented as a sparse combinations of atoms from a dictionary. Dictionary learning describes the acquisition process of the underlying dictionary for a given set of training samples. While ideally this would be achieved by optimizing the expectation of the factors over the underlying distribution of the training data, in practice the necessary information about the distribution is not available. Therefore, in real world applications it is achieved by minimizing an empirical average over the available samples. The main goal of this paper is to provide a sample complexity estimate that controls to what extent the empirical average deviates from the cost function. This estimate then provides a suitable estimate to the accuracy of the representation of the learned dictionary. The presented approach exemplifies the general results proposed by the authors in [1] and gives more concrete bounds of the sample complexity of dictionary learning. We cover a variety of sparsity measures employed in the learning procedure.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Rémi Gribonval Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 6:44:40 PM
Last modification on : Monday, June 27, 2022 - 3:07:05 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:50:32 PM


Files produced by the author(s)



Matthias Seibert, Martin Kleinsteuber, Rémi Gribonval, Rodolphe Jenatton, Francis Bach. On The Sample Complexity Of Sparse Dictionary Learning. SSP 2014 - IEEE Workshop on Statistical Signal Processing, Jun 2014, Jupiters, Gold Coast, Australia. ⟨10.1109/SSP.2014.6884621⟩. ⟨hal-00990684⟩



Record views


Files downloads