Online Dictionary Learning for Sparse Coding

Julien Mairal & Francis Bach & Jean Ponce & Guillermo Sapiro

Introduction

Sparse coding means modeling data vector as sparse linear combinations of basis elements. In this paper, the author proposed a method that can do online dictionary learning, means if there is a new data, we don't have to retrain the model from the beginning.

Classical Dictionary Learning Techniques

The model introduced above is called 'Dictionary', represented by D. We want to find the difference between the original data and the data recovered from D, then formulate a cost function.

The difference (or distance) function is

We use this difference function to formulate the empirical cost function

Because we don't want the length of alpha term and D term become too long, we added the regularization term and constrain

However, the difference function above is not convex, we adjusted it to 

which is convex.

Then the author said that we are usually not interested in a perfect minimization of the empirical cost function, but in the minimization of the expected cost function

means that we don't train the dictionary with all data points. We just sample some data point x to do the training. 

The process of training dictionary - proposed by other author - is as following:

Online Dictionary Learning

The algorithm is summarized as following:

To do step 7, we need algorithm 2

Result