# 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** = [**y**_{1} ... **y**_{N}] 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, min_{D,X} ||**X**||_{1} s.t. **D**∈*D, ***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.

## Achievements

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.

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 |

## More details