 # Nuclear Norm minimization subject to constraint

How to solve the problem using CVX.

We have a few observations of a matrix. Lets denote it by “D”. Since the observations are not accurate and some measurement error is involved, I want to solve this optimization problem: -

min_Z ||Z||_N such that ||E.*Z-D||_F<= epsilon.

Here Z is a matrix variable of dimension same as D.
E.*Z is the hadamard product of Z with E. And E represents the measurement matrix.
|| ||_N represents nuclear norm.
|| ||_F represents frobenious norm.

Now I typed something like this in my matlab code: -

        cvx_begin sdp
variable Z(m,n) semidefinite;
norm(G.*Z(m,n)-D,'fro') <= epsilon ;
minimize(norm_nuc(Z(m,n)))
cvx_end


Its not working. I think I made some mistake. I will be really grateful if someone show me the right way to implement the optimization using CVX.
Thank you!
Shantanu.

Do you want (require) Z to be semidefinite? If not, don’t include that, and of course that only makes sense if m = n.

Other than the variable declaration line
variable Z(m,n)
the other uses of Z should be to Z, not Z(m,n), the latter of which is only the (m,n) element of Z, rather than the full matrix Z, which is what you want.

Presuming you don’t want a semidefinite constraint:

cvx_begin
variable Z(m,n)
norm(G.*Z-D,'fro') <= epsilon ;
minimize(norm_nuc(Z))
cvx_end

Thank you Mark.
I don’t need Z to be semidefinite.
I have a question I need to solve matrices of dimension 1000 \times 1000.
But CVX is taking a lot of time. Is there anything we can do to speed up the process.
I mean any other way of solving this problem.

Perhaps there is a more specialized tool which is faster, but I don’t have a specific one to recommend. CVX is generally not the fastest way to solve a problem in terms of computer time. Mosek is likely to be the best solver available under CVX for your problem (the other commercial solver available under CVX, Gurobi, can’t be used for this problem due to not having semidefinite cone capability which is required for norm_nuc).