Personal tools

Dictionary Learning Theory

Can we learn a dictionary from training samples with performance guarantees?

Dictionary Learning Theory

Can we robustly identify an underlying ideal dictionary D, given a set Y = [y1 ... yN] of training data available in limited quantity and/or corrupted by noise or outliers?

This has been investigated under a theoretical framework based on L1 minimization, minD,X ||X||1 s.t. DD, Y=DX, which is non-convex in this context.

The robustness of the approach to non-sparse outliers and limited training data has been proved under certain probabilistic scenarios.


The local correctness of the approach has been proved under certain probabilistic scenarios (Bernoulli-Gaussian coefficients X) for square dictionaries.

  • Robustness to the presence of outliers (non-sparse training samples) is proved assuming the ground truth dictionary is sufficiently incoherent;
  • Robustness to the limited amount of training data is proved provided the number N of training samples exceed     N ≥CKlogK     where K is the number of atoms of the dictionary and the constant C depends on a parameter of the Bernoulli-Gaussian distribution which drives the sparsity of the training set.


Robust dictionary learning from training samples with outliers.

Source: Gribonval and Schnass 2010

 training-set-with-outliers l1-learning-cost-function

Bernoulli-Gaussian training samples include boths sparse vectors (aligned on low dimensional subspaces) and outliers.With high probability, local minima of the L1 cost function are global minima identifying the ground truth dictionary

The minima of the L1 criterion identify the dictionary with high probability, for dictionaries with low enough coherence μ / small enough Bernoulli-Gaussian parameter p (p drives the sparsity level and the proportion of non-sparse outliers).


More details



RĂ©mi Gribonval, coordinator
Equipe-Projet METISS
INRIA Rennes - Bretagne Atlantique
Campus de Beaulieu
F-35042 Rennes cedex, France.

Phone: (+33/0) 299 842 506
Fax: (+33/0) 299 847 171
E-MAIL: contact