1

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.

Gilles
  • 253
  • 1
  • 2
  • 10
Excalibur
  • 113
  • 4
  • 1
    The square root of an spd matrix is a matrix. How does it make sense to minimize a matrix expression? – Kirill Oct 24 '14 at 07:16
  • 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! – Excalibur Oct 24 '14 at 15:37
  • @DavidKetcheson , sorry, A is outside the square root, I updated my question. Thanks for help! – Excalibur Oct 24 '14 at 17:01
  • Also, I think you mean sqrtm(), not sqrt. – David Ketcheson Oct 24 '14 at 17:08
  • @DavidKetcheson It is matrix muplication, just $X^{T}X$. – Excalibur Oct 24 '14 at 17:09
  • @DavidKetcheson I think it is still sqrt, as sqrtm() will give me a different kind of error. The background is: the nuclear norm of a matrix X is $nuc_norm(X)=trace(sqrt(X'*X))$ , but now I am not minimize the nuc_norm. – Excalibur Oct 24 '14 at 17:15
  • @Excalibur: I'm pretty sure you mean sqrtm not sqrt too, and according to http://scicomp.stackexchange.com/questions/5503 cvx has trace_sqrtm but this is not exactly what you need. – k20 Oct 24 '14 at 17:20
  • @DavidKetcheson Seems you are right! Thanks very much! But I am still have problem to solve it by CVX. – Excalibur Oct 24 '14 at 17:27
  • a question on math.stackexchange seems related http://math.stackexchange.com/questions/239352/trace-minimization-with-constraints – k20 Oct 24 '14 at 17:28
  • @k20 Thanks, seems related. I will looking into it! – Excalibur Oct 24 '14 at 19:12
  • @Excalibur I see in your other question that your function is called Test_WeightNucNorm. If the nuc norm is trace_sqrtm(X' X) then is 'WeightNucNorm' trace(sqrtm(X' X) * A) where matrix A somehow involves weights? Is it a diagonal matrix of non-negative weights? If so, you could try sum(diag(sqrtm(X' X)) * diag(A)). – k20 Oct 24 '14 at 22:30
  • Oh right sqrtm is not in cvx. But if A is a diagonal matrix of weights, what about something like trace_sqrtm((XA)'(XA))? – k20 Oct 24 '14 at 22:40
  • ...which would be norm_nuc(XA). – k20 Oct 24 '14 at 23:14
  • @k20 you are totally right! Yes, A is a diagnal non-negative weights matrix. However, norm_nuc(X*A) is not equivalent with sum(diag(sqrtm(X' X)) * diag(A)). What I need is the equivalent representation with sum(diag(sqrtm(X' X)) * diag(A)), but I haven't found a valid representation for CVX yet. – Excalibur Oct 24 '14 at 23:33
  • @Excalibur: you're right, my math was wrong. – k20 Oct 25 '14 at 00:25

2 Answers2

2

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.

k20
  • 772
  • 3
  • 3
  • 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! – Excalibur Oct 25 '14 at 00:56
  • 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. – k20 Oct 25 '14 at 01:09
  • 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. – k20 Oct 25 '14 at 01:23
  • Hi @k20 , oh, you are totally right! My mistake is: what I get is the weighted trace, not weighted nuclear norm!! – Excalibur Oct 25 '14 at 01:58
  • Hi @k20 , thanks very much!! Your observation is great! Now my problem should be how to represent the weighted nuclear norm ... – Excalibur Oct 25 '14 at 02:06
  • @Excalibur: As I mention in my answer, you can't represent the weighted nuclear norm in a way that cvx will solve it, because it is not convex or concave. You will need to use a different method to solve the minimization. – k20 Oct 25 '14 at 02:15
  • Hi @k20 , thanks, so that I should refer to other possible ways to solve my problem. – Excalibur Oct 25 '14 at 02:17
1

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.

Brian Borchers
  • 18,719
  • 1
  • 39
  • 70
  • 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? – Excalibur Oct 24 '14 at 16:39
  • Sorry- I had misread your question as involving the square root of a scalar expression. – Brian Borchers Oct 25 '14 at 04:18