Online Dictionary Learning for Sparse Coding

Julien Mairal, Francis Bach, Jean Ponce and Guillermo Sapiro

Abstract

In sparse coding, where each training example is represented by sparse linear combination of basic elements, which forms a dictionary, a learned dictionary, is shown to have better performance over a pre-defined one. Though, evidences have demonstrated that learned dictionaries are crucial to achieve state-of-art results, the optimization problem one has to deal with is often the bottle neck and limits the more ubiquitous utilization. 

The authors proposed a online learning method, which hopefully solved problems often encountered in several dictionary learning algorithms such as too big a training set and a dynamic changing one. Basically, it harnesses the stochastic gradient descent, which is shown to often be the fastest in terms of convergence though not good conventionally, by taking an example (or a tiny set) a time. 

In a typical dictionary learning, one tries to minimizes the differences between training example and its sparse representation as shown in the first equation, which is equivalent to solving the one below, where D is the dictionary and alpha a slack variable ensuring sparsity. In the paper, the authors proposed a method iteratively solving D and alpha given the other fixed, which in the paper is proven of convergence. The authors also suggested several side methods to boost the performance.

Contributions

1. Propose a method that is faster in both small and large training set than previous methods and show it could be used on real case such as removing imprinting of images.
2. Cast dictionary learning problem as a optimization of a non-convex objective function over a convex set