0
$\begingroup$

I have a question about using nuclear norm for rank minimisation.

I have a SDP problem.

enter image description here f(X) is convex in nature and g(x) is linear.

Now, I must apply rank minimisation and establish a relationship between X and x. So, can I apply

Norm_nuc(X) - norm(x)^2_l2<= 0

I employ first-order Taylor series approximation for norm(x)^2_l2 to make it linear. The problem is convex and solved using cvx. But I must ask experts if this is a relèvent and correct constraint.

Improve this question
$\endgroup$
5
  • $\begingroup$ If x is a declared variable, which it should be, I don't see how that constraint would be accepted by CVXPY, or any other DCP tool, unless you invoked DCCP. Where does L2 norm come from? Perhaps you want to minimize (some multiple of) norm_nuc, or maximize its negative,, as at least a term in the objective function? Do you also include the SDP constraint? You haven't told us what f(X,x) is. As it stands, it's not clear what your original optimization problem is, or what your proposed formulation is. I presume rank minimization is to try to induce $X=xx^T$ to be satisfied by solution. $\endgroup$
    – Mark L. Stone
    Commented Aug 12 at 16:56
  • $\begingroup$ @MarkL.Stone please have a look at the problem now. $\endgroup$
    – Muhammad
    Commented Aug 12 at 17:22
  • $\begingroup$ Perhaps you can tell us explicitly what f(X) and g(x) are? Are those Norm_nuc(X) and norm(x)^2_l2, and if so, are they part of your original problem, or introduced somehow as part of your rank minimization to try to induce rank one solution of what appears to be SDP relaxation of $X = xx^T$? $\endgroup$
    – Mark L. Stone
    Commented Aug 12 at 17:33
  • $\begingroup$ The rank minimization constraint does not induce them but is part of the original problem. To be exact, its X(n,n)<= (a-b)/a + real(x(n)) and n =1,..., N, a, b are real numbers and Norm_nuc - (x)^2_l2 is introduced as an additional constraint which is to have this relaxation control X>=xx^T and also at the same time helping me to get a rank-1 solution. So, I am getting x as a rank-1 solution, which perfectly aligns with the solution I need. $\endgroup$
    – Muhammad
    Commented Aug 12 at 17:53
  • $\begingroup$ If that limesarized (norm^2) upper bound on norm_nuc(X) results in a rank one solution, then you have succeeded. The only danger would be that you might be overconstraining X, and therefore not getting as good a solution (as low an objective function) as you (perhaps) could have To further investigate that, you could relax that norm_nuc constraint by adding something to the RHS, and see whether you still get a rank one solution, and if so, whether it is better (smaller objective value) than the solution you are now getting. Alsocan eliminate norm_nuc constraint and see whether still rank 1 $\endgroup$
    – Mark L. Stone
    Commented Aug 12 at 18:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.