# 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.

## 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):

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