# 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[1] >= ... >= 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?