# Represent Schatten-p norm in CVX

I know that the CVX function

norm_nuc(X)


is the nuclear norm of X, which is also Schatten-1 norm. For Frobenius Norm (or Schatten-2 norm), it is represented by

norm(X,'fro')


But how can I represent the general Schatten-p norm for 1<p<2 in CVX?

I do not believe it is possible.

@mcg Really? Well, such a bad news.

If CVX could solve everything (or even just everything convex), what would people write journal articles about? @mcg Yeah, you are right! Thanks!

Actually, any symmetric monotone function of the singular values of a matrix is DCP-representable. See Ben-Tal and Nemirovski “Lectures on Modern Convex Optimization”, Proposition 4.2.2. But the best representation (presented there, at least) is huge!

Let’s see how this works for a PSD matrix A. (The case of rectangular matrices is similar.)

• the sum S_k(A) of the top k eigenvalues of A is the solution to the problem
minimize sk + Tr(Z)
subject to
Z ⪰ 0
A ⪰ 0
Z + sI ⪰ A

• g(\lambda(A)) is the solution to the problem
minimize g(s)
subject to
s >= ... >= s[n]
S_k(A) <= s[1:k],  k = 1, ..., n
trace(A) == sum(s)


The only difficulty is that this representation introduces a new n x n PSD variable for each eigenvalue, resulting in a problem with n n x n SDP constraints — which is not exactly fast to solve.

2 Likes

This is great, Madeleine. Of course, we do have the sum of the top k eigenvalues in A. I’d say that even though this corrects my claim that it is not possible, it is certainly not practical for all but the smallest matrices… If someone were to implement this, it would be interesting to see!

What kind of run times for some representative problems?