1
$\begingroup$

I want to minimize $f(x) = \mathrm{Tr}(\sqrt{\mathbf{X}^{T}\mathbf{X}}\mathbf{A})$, where $\mathbf{X}$ is an matrix variable of dimension $d \times d$, and $\mathbf{A}$ is a known matrix. I tried the following code:

cvx_begin
    variable x(d,d)
    minimize(trace(sqrt(sum_square_abs(x))*A)) 
    subject to
        x(sp_index) == M(sp_index)
cvx_end

However, there are still errors as following:

Error using cvx/sqrt (line 61)
Disciplined convex programming error:
Illegal operation: sqrt( {convex} ).

Error in Test_CVX_Iterative_Optimal (line 34)
    minimize(trace(sqrt(sum_square_abs(x))*A)) 

So how should I solve this problem by CVX? Looking forward to your reply! I also asked the same question in the CVX forum http://ask.cvxr.com/question/2894 but haven't got it solved yet. Wish anyone here is able to offer help!


Update: Thanks to @DavidKetcheson , I should use sqrtm() rather than sqrt. To represent $\mathrm{Tr}(\sqrt{\mathbf{X}^T\mathbf{X}})$ I should use trace_sqrtm(sum_square_abs(x)). However, I need to represent $\mathrm{Tr}(\sqrt{\mathbf{X}^T\mathbf{X}}\mathbf{A})$, and I don't know how to represent it by a valid CVX expression.


I tried

minimize(trace(sqrtm(sum_square_abs(x))*A))

to replace sqrt in the original, but I got the following error

Undefined function 'schur' for input arguments of type 'cvx'.

Error in sqrtm (line 32)
[Q, T] = schur(A,'complex');  % T is complex Schur form.

Error in Test_WeightNucNorm (line 35)
        minimize(trace(sqrtm(sum_square_abs(x))*A))

I understand now that sqrtm() function is not implemented in CVX, so I have the error ' Undefined function 'schur' for input arguments of type 'cvx'.'. But my problem is still not solved.


I think I should use:

minimize(trace_sqrtm(sum_square_abs(x))*A)

But I still get error:

Error using cvx/trace_sqrtm (line 9)
Input must be affine.

Error in Test_WeightNucNorm (line 40)
        minimize(trace_sqrtm(sum_square_abs(x))*A)

---------- Important update Thanks to @k20 , I made a mistake!! This is not the weighted nuclear norm of matrix $\mathbf{X}$, but the weighted trace of $\sqrt{\mathbf{X}^T\mathbf{X}}$!! Now my problem becomes that:how to represent the weighted nuclear norm of a matrix $\mathbf{X}$, where $\mathbf{X}$ is CVX variable, $\mathbf{A}$ is a diagonal weight matrix. I tried to find a CVX function which give me all the singular values of variable $\mathbf{X}$, but I haven't found such a function.

$\endgroup$
  • 1
    $\begingroup$ The square root of an spd matrix is a matrix. How does it make sense to minimize a matrix expression? $\endgroup$ – Kirill Oct 24 '14 at 7:16
  • $\begingroup$ Hi @Kirill , thanks for help! My previous question is aimed to simplified my question and show the key problem. I updated my question. Can you check it? Thanks! $\endgroup$ – Excalibur Oct 24 '14 at 15:37
  • $\begingroup$ @DavidKetcheson , sorry, A is outside the square root, I updated my question. Thanks for help! $\endgroup$ – Excalibur Oct 24 '14 at 17:01
  • $\begingroup$ Also, I think you mean sqrtm(), not sqrt. $\endgroup$ – David Ketcheson Oct 24 '14 at 17:08
  • $\begingroup$ @DavidKetcheson It is matrix muplication, just $X^{T}X$. $\endgroup$ – Excalibur Oct 24 '14 at 17:09
2
$\begingroup$

I'm going to boldly say that you are doing it wrong, because your goal is to minimize a weighted nuclear norm but your equations don't agree. The nuclear norm is the sum of singular values. The weighted nuclear norm is the weighted sum of singular values. If your matrix A is intended to be the diagonal matrix of singular value weights, then I don't think your equation represents the correct weighted sum.

The response to the question http://ask.cvxr.com/question/1708/maximize-the-minimum-singular-value/ suggests that the minimum singular value is not a convex or concave function so cvx can't deal with it. Therefore it seems unlikely that cvx can deal with an arbitrary weighted sum of singular values, as would be required by a weighted nuclear norm.

$\endgroup$
  • $\begingroup$ Hi @k20 , as $norm_nuc(x)=trace(\sqrt{x^Tx})$, so that I think the weighted nuclear norm is $trace(\sqrt{x^Tx}*A)$ as $A$ is a diagonal weight matrix. Is this wrong? Thanks for your help! $\endgroup$ – Excalibur Oct 25 '14 at 0:56
  • $\begingroup$ Yes it is wrong. Pick a matrix X and compute trace(sqrtm(X' X)) and you will see that this is the sum of the singular values s of X. Then pick some weights w and define A as the corresponding diagonal matrix. You will see that trace(sqrtm(X' X) * A) does not equal the weighted nuclear norm (the dot product of s with w), except in special cases like when A is the identity matrix. $\endgroup$ – k20 Oct 25 '14 at 1:09
  • $\begingroup$ An easy example is when X is diagonal. The weighted nuclear norm should not be affected by permuting X but the thing that you are computing is affected. $\endgroup$ – k20 Oct 25 '14 at 1:23
  • $\begingroup$ Hi @k20 , oh, you are totally right! My mistake is: what I get is the weighted trace, not weighted nuclear norm!! $\endgroup$ – Excalibur Oct 25 '14 at 1:58
  • $\begingroup$ Hi @k20 , thanks very much!! Your observation is great! Now my problem should be how to represent the weighted nuclear norm ... $\endgroup$ – Excalibur Oct 25 '14 at 2:06
1
$\begingroup$

minimizing $\sqrt{f(x)}$ is equivalent to minimizing $f(x)$ as long as $f(x) \geq 0$ because taking the square root is a monotone transformation. Just remove the square root from your objective function.

$\endgroup$
  • $\begingroup$ Hi @BrianBorchers, thanks for your help! I updated my question. My previous simplified question was aimed to show the key problem, but it leads a simple solution you mentioned. I need to minimize $trace(\sqrt{(X′X)}A)$, in this way, the $\sqrt{ } $ cannot be removed. Do you know how to express it by an expression that CVX will accept? $\endgroup$ – Excalibur Oct 24 '14 at 16:39
  • $\begingroup$ Sorry- I had misread your question as involving the square root of a scalar expression. $\endgroup$ – Brian Borchers Oct 25 '14 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.