Weighed Nuclear Norm Minimization using CVX

Dear all,

I am looking to solve weighted nuclear norm minimization problem using CVX. I wonder if CVX in-built has a function written to solve the mentioned problem. Or if anyone has written a script to solve the problem, I would be very grateful if it can be shared.

Thank you very much in advance,

Please provide more details on the exact problem you wish to solve, and the properties (see below) of the weights.

As discussed in my post at Maximize the minimum singular value , the minimum singular value (for matrix dimension > 1) is neither convex nor concave. The minimum singular value is the special case of weighted nuclear norm having weight = 1 on the minimum singular value and weight = 0 on all other singular values. Therefore, the general weighted nuclear norm is not convex, and therefore can not be handled in CVX.

However, see the comments by Michael Grant, the CVX developer, at https://math.stackexchange.com/questions/1081446/how-is-the-nuclear-norm-convex-whereas-the-weighted-nuclear-norm-is-not , discussing the requirements on the weights in order for the weighted nuclear norm to be convex.

Also see sections 2.2.1, 2.2.2, 2.2.3 of “Weighted Nuclear Norm Minimization with Application to Image Denoisin” Gu, Zhang et al http://www4.comp.polyu.edu.hk/~cslzhang/paper/WNNM.pdf .relating to ordering of weights.

1 Like

I have checked the links and references. So, in our problem, we also have non-increasing weights. As shown in Gu. Zhang at al paper, if weights are non-increasing then the problem is convex and there exists a global solutions. Our problem is as follows:

min_X ||X||_w* (which is the weight nuclear norm, i.e., w(i)sigma(i), where sigma(i) are the singular values of X and sigma(i) >= sigma(i+1) and w(i) >= w(i+1))

subject to
A*vec(X) == b, where vec(X) is the vectorization of X.

If the problem is just minimization the nuclear norm; that means all weights are one, then we can solve this using cvx quite easily. However, do you have any suggestion how to solve using CVX when weights are not equal but non-increasing order.

I’ll let you study the Gu. Zhang at al paper to determine whether there is an approach in there to suit your needs. If someone else wants to plop in here, they’re more than welcome, but I wouldn’t count on it.