Low rank approximation using CVX

1

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© = 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? Please help.Thanks.

1 Like
2

Well, the “why” is really outside the scope of this forum. Indeed if I was being strict today I’d close the topic.

But it being Sunday, I will give you the short answer: because nuclear norm minimization is not guaranteed to return the lowest-rank solution in general. It does under certain conditions, sure, but apparently those conditions are not satisfied in this case.

And with that, I will instruct you to take this to another forum, such as Math StackExchange or OR-Exchange, where you can pose this question in a more proper venue. After all, this forum is focused on the software; and by your own admission, it has done its job. These other forums are better suited for discussion the mathematics—if for no other reason than there are more mathematicians here. We don’t have the brainpower for you here! (Speaking for myself.)

1 Like