Low rank approximation using CVX toolbox in Matlab

Question

I try to use CVX toolbox to do "low rank approximation" work. The code is as follows:

r = 2; % the rank;
N = 32; % the dimension
M = 32;
a = randn(N,r);
b = randn(M,r);
X = a*b'; % low rank Matrix;
A = rand(20,N);
Y = A*X;
% low rank approximation using nuclear norm
cvx_begin
variable Xe(N,M)
minimize norm_nuc(Xe);
subject to A*Xe == Y;
cvx_end

Then Matlab tells me that

number of iterations = 8 primal objective value = 5.75866738e+01 dual objective value = 5.75866738e+01 gap := trace(XZ) = 3.73e-08 relative gap = 3.21e-10 actual relative gap = 3.49e-10 rel. primal infeas (scaled problem) = 6.90e-11 rel. dual " " " = 1.50e-12 rel. primal infeas (unscaled problem) = 0.00e+00 rel. dual " " " = 0.00e+00 norm(X), norm(y), norm(Z) = 8.4e+01, 1.6e+00, 4.2e+00 norm(A), norm(b), norm(C) = 6.0e+01, 1.6e+02, 5.1e+00 Total CPU time (secs) = 1.75 CPU time per iteration = 0.22 termination code = 0

DIMACS: 4.9e-10 0.0e+00 3.8e-12 0.0e+00 3.5e-10 3.2e-10 Status: Solved

Optimal value (cvx_optval): +57.5867

Obviously, CVX works well and the job has been done. However, the estimated results "Xe" does not equal to the original matrix "X". Why?

Some papers have proven that "Xe" should be equal to "X", such as "Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization,Benjamin Recht, Maryam Fazel, Pablo A. Parrilo, 2008".

Answer 1

I think the main problem comes from the measurement you calculated:

A = rand(20,N);
Y = A*X; 

First of all the number of measurements needed to exact recovery is in order or O(rN) which is at least 2 * 32, so your number of measurements is too small to get a correct result.

Also the linear operator you use is not the general way that people used on low rank matrix recovery case, try y = A*X(:) , note that 'X(:)' is the operator that makes matrix X into a long vector by listing the columns of it. So you should make A being a matrix that match the dimension

r = 2; % the rank;
n = 32; % the dimension

a = randn(n,r);
b = randn(n,r);
X = a*b'; % low rank Matrix;

m=fix(n^2-1);
A = randn(m, n^2);
y = A*X(:);
% low rank approximation using nuclear norm

cvx_begin
variable Xe(N,M)
minimize norm_nuc(Xe)
subject to
A*Xe(:)==y
cvx_end

error = norm(X-Xe)