Demo: Matrix Completion
This short demo shows how to use TFOCS to perform nuclear norm minimization. Nuclear norm minimization is used for recovering all the entries of a partially observed low-rank matrix.
Contents
Setup a problem
rng(234923); % for reproducible results N = 16; % the matrix is N x N r = 2; % the rank of the matrix df = 2*N*r - r^2; % degrees of freedom of a N x N rank r matrix nSamples = 3*df; % number of observed entries % For this demo, we will use a matrix with integer entries % because it will make displaying the matrix easier. iMax = 5; X = randi(iMax,N,r)*randi(iMax,r,N); % Our target matrix
Now suppose we only see a few entries of X. Let “Omega” be the set of observed entries
rPerm = randperm(N^2); % use "randsample" if you have the stats toolbox
omega = sort( rPerm(1:nSamples) );
Print out the observed matrix in a nice format. The “NaN” entries represent unobserved values. The goal of this demo is to find out what those values are!
Y = nan(N);
Y(omega) = X(omega);
disp('The "NaN" entries represent unobserved values');
disp(Y)
The "NaN" entries represent unobserved values
30 NaN 24 8 12 14 12 NaN 22 NaN NaN 10 14 24 20 NaN
30 21 NaN 11 21 NaN 12 21 NaN 15 17 NaN 8 15 23 NaN
NaN 9 NaN NaN 9 NaN NaN NaN 7 9 8 7 5 NaN 11 6
35 NaN NaN 10 NaN NaN NaN NaN 23 NaN 17 13 15 26 24 NaN
NaN 9 9 5 NaN NaN NaN NaN NaN 9 8 NaN NaN 9 11 NaN
NaN 11 19 7 NaN 13 10 11 17 19 12 9 11 19 17 NaN
45 24 30 NaN NaN 29 18 NaN 25 30 NaN 19 17 30 32 NaN
NaN NaN 21 NaN 15 18 12 15 18 21 15 12 12 21 21 12
25 11 NaN 7 11 13 10 11 17 19 12 9 NaN 19 NaN NaN
NaN 13 11 7 13 16 8 NaN 8 11 11 NaN NaN 11 15 8
45 24 30 14 24 29 18 24 25 30 23 19 17 NaN 32 18
NaN 15 21 9 NaN 18 12 15 18 21 15 12 NaN 21 21 12
25 NaN 13 9 17 NaN 10 17 NaN 13 14 13 7 13 19 10
40 20 28 12 20 NaN 16 20 NaN NaN NaN 16 16 NaN 28 16
NaN NaN 18 10 18 22 12 NaN 14 NaN 16 14 10 NaN 22 12
25 11 19 7 11 NaN 10 NaN NaN NaN NaN 9 11 19 17 NaN
Matrix completion via TFOCS
We use nuclear norm relaxation. There are strong theorems that show this relaxation will usually give you the exact original low-rank matrix provided that certain conditions hold. However, these conditions are generally not possible to check ‘a priori’, so I cannot guarantee that this will work. But by choosing enough measurements, it becomes increasingly likely to work.
% Add TFOCS to your path (modify this line appropriately): addpath ~/Dropbox/TFOCS/ observations = X(omega); % the observed entries mu = .001; % smoothing parameter % The solver runs in seconds tic Xk = solver_sNuclearBP( {N,N,omega}, observations, mu ); toc
Auslender & Teboulle's single-projection method Iter Objective |dx|/|x| step ----+---------------------------------- 100 | +3.54125e+02 1.68e-04 1.32e-03 200 | +3.54125e+02 7.42e-07 1.77e-03* 251 | +3.54125e+02 5.41e-09 2.28e-03* Finished: Step size tolerance reached Elapsed time is 1.289716 seconds.
To display the recovered matrix, let’s round it to the nearest .0001 so that it displays nicely:
disp('Recovered matrix (rounding to nearest .0001):') disp( round(Xk*10000)/10000 ) % and for reference, here is the original matrix: disp('Original matrix:') disp( X ) % The relative error (without the rounding) is quite low: fprintf('Relative error, no rounding: %.8f%%\n', norm(X-Xk,'fro')/norm(X,'fro')*100 );
Recovered matrix (rounding to nearest .0001):
30 12 24 8 12 14 12 12 22 24 14 10 14 24 20 12
30 21 15 11 21 26 12 21 10 15 17 16 8 15 23 12
15 9 9 5 9 11 6 9 7 9 8 7 5 9 11 6
35 16 26 10 16 19 14 16 23 26 17 13 15 26 24 14
15 9 9 5 9 11 6 9 7 9 8 7 5 9 11 6
25 11 19 7 11 13 10 11 17 19 12 9 11 19 17 10
45 24 30 14 24 29 18 24 25 30 23 19 17 30 32 18
30 15 21 9 15 18 12 15 18 21 15 12 12 21 21 12
25 11 19 7 11 13 10 11 17 19 12 9 11 19 17 10
20 13 11 7 13 16 8 13 8 11 11 10 6 11 15 8
45 24 30 14 24 29 18 24 25 30 23 19 17 30 32 18
30 15 21 9 15 18 12 15 18 21 15 12 12 21 21 12
25 17 13 9 17 21 10 17 9 13 14 13 7 13 19 10
40 20 28 12 20 24 16 20 24 28 20 16 16 28 28 16
30 18 18 10 18 22 12 18 14 18 16 14 10 18 22 12
25 11 19 7 11 13 10 11 17 19 12 9 11 19 17 10
Original matrix:
30 12 24 8 12 14 12 12 22 24 14 10 14 24 20 12
30 21 15 11 21 26 12 21 10 15 17 16 8 15 23 12
15 9 9 5 9 11 6 9 7 9 8 7 5 9 11 6
35 16 26 10 16 19 14 16 23 26 17 13 15 26 24 14
15 9 9 5 9 11 6 9 7 9 8 7 5 9 11 6
25 11 19 7 11 13 10 11 17 19 12 9 11 19 17 10
45 24 30 14 24 29 18 24 25 30 23 19 17 30 32 18
30 15 21 9 15 18 12 15 18 21 15 12 12 21 21 12
25 11 19 7 11 13 10 11 17 19 12 9 11 19 17 10
20 13 11 7 13 16 8 13 8 11 11 10 6 11 15 8
45 24 30 14 24 29 18 24 25 30 23 19 17 30 32 18
30 15 21 9 15 18 12 15 18 21 15 12 12 21 21 12
25 17 13 9 17 21 10 17 9 13 14 13 7 13 19 10
40 20 28 12 20 24 16 20 24 28 20 16 16 28 28 16
30 18 18 10 18 22 12 18 14 18 16 14 10 18 22 12
25 11 19 7 11 13 10 11 17 19 12 9 11 19 17 10
Relative error, no rounding: 0.00000410%
Published with MATLAB® 7.12