Online dictionary learning for sparse coding

Sparse coding—that is, modelling data vectors as sparse linear combinations of basis elements.

This paper focuses on learning the basis set, also called dictionary, to adapt it to specific data, and propose an online optimization algorithm for dictionary learning, based on stochastic approximations.


Most recent algorithms for dictionary learning are second-order iterative batch procedures, accessing the
whole training set at each iteration in order to minimize a cost function under some constraints.
They cannot effectively handle very large training sets, or dynamic training data changing over time,

This paper makes three main contributions.

1. Cast  the dictionary learning problem as the optimization of a smooth nonconvex objective function over a convex set,
2. Propose in  an iterative online algorithm that solves this problem by efficiently minimizing at each step a quadratic surrogate function of the empirical cost over the set of constraints. 
3. The algorithm is significantly faster than previous approaches to dictionary learning on both small and large datasets of natural images.

 Optimizing the Algorithm

Handling Fixed-Size Datasets.

In practice, although it may be very large, the size of the training set is often finite

Mini-Batch Extension.

Improve the convergence speed of our algorithm by drawing η > 1 signals at each iteration instead of a single one, which is a classical heuristic in stochastic gradient descent algorithms.

Purging the Dictionary from Unused Atoms. 

Every dictionary learning technique sometimes encounters situations
where some of the dictionary atoms are never (or very seldom) used, which happens typically with a very bad intialization.