[ammai2016] Online Dictionary Learning for Sparse Coding

Date: March 17th, 2016

Title: Online Dictionary Learning for Sparse Coding

Author: Julien Mairal, et al

Novelties:

1. Introduce a way to learn dictionary which is online and can apply on large dataset.

Contributions:

There are three contributions:
1. They ast the dictionary learning problem as the optimization of a smooth nonconvex objective function over a convex set.
2. They propose an iterative online algorithm to solve it.
3. Through experiments, the algorithm is faster than state-of-the-art.

Technical Summarizes:

The online dictionary learning algorithm:

We have a quardratic function:

This function aggregate the past information and is the upperbound of the empirical cost function.
Since the value of the function in neighbor iteration are close, we can obtain Dt with previous one as warm restart:

Then they introduce some practically improvement on this algorithm.

Experiments:

The dataset is images from Berkeley segmentation dataset, 1,000,000 for training and 250,000 for testing.

The top is online compares with batch settings, the bottom is their method compares with SG ways.