Dictionary Learning with CVX Toolbox

In this post we do an exercise that help you implement sparse coding and dictionary learning without using algorithms dedicated to optimizing a -regularized least squares problem. We will use a generic convex optimization CVX toolbox for sparse encoding and adopt simple updating rule for dictionary .

For simplicity, a single image “lena” is used to learn the dictionary. Firstly, patches are extracted and normalized:

clear all;
I=double(imread('lena.png'))/255;
% extract 8 x 8 patches
X=im2col(I,[8 8],'sliding');
X=X-repmat(mean(X),[size(X,1) 1]);
X=X ./ repmat(sqrt(sum(X.^2)),[size(X,1) 1]);
X=X(:,1:100:end);

Since the number of patches is so huge, we just sub-sample 1%. This is enough for us to check the correctness of our algorithm.

Next, the number of iterations, dictionary size, and regularization coefficient are set:

nIter = 25;
gamma = .15;
p = 200;

% init dictionary
sel = randperm(size(X,2));
sel = sel(1:p);
D = X(:,sel);
n = size(X,2);
%D = D ./ repmat( sqrt(sum(D.^2)), [w^2, 1] );
S = zeros(p,n);

We individually encode each of input sample by optimizing the following objective function:

cvx_begin quiet
variable s(p);
minimize (.5*norm(X(:,j)-D*s) + gamma*norm(s,1));
cvx_end

In order to update , we just need to solve a least squares problem:

This objective function can be solved easily by taking the first-order derivative respect to :

If the Hessian is positive semidefinite, the above quadratic form reachs its global minimum value with the minimizer:

There is the case that will grow big and shrinks small to fit . In order to prevent it from happenning, a -norm applied for dictionary atoms is neccessary:

The Matlab code is very simple:

D = X * pinv(S);
D=D ./ repmat(sqrt(sum(D.^2)),[size(D,1) 1]);

After iterations, we can visualize the content of dictionary atoms by calling from SPAMS Toolbox:

ImD=displayPatches(D);
figure, imagesc(ImD); colormap('gray');

The result after 6 hours training (!) is displayed below:

Learned dictionary from Lena image with 100 atoms