Computing or bounding a modified Ky Fan norm


#1

The Ky Fan k-norm of a matrix X \in M_n is defined as follows:

\|X\|_k := \sum_{i=1}^k \sigma_i^\downarrow(X)

(i.e., the sum of the k largest singular values of X). In CVX, there is a simple way to optimize over the set of matrices with bounded Ky Fan k-norm. For example, if we wanted to optimize over the set of matrices with Ky Fan k-norm no larger than 1, we could set one of the constraints in CVX as follows:

lambda_sum_largest([zeros(n),X;X',zeros(n)],k) <= 1;

My question is whether or not there is a similarly simple way to implement the following norm in CVX:

\|X\|_{(k,2)} := \sqrt{\sum_{i=1}^k (\sigma_i^\downarrow(X))^2}

That is, I am interested in the 2-norm of the k largest singular values instead of the 1-norm of the k largest singular values.


Using svds(A,k)
(Michael C. Grant) #2

I am not aware of a way to do this, no. You would need to be able to express the epigraph of this norm using semidefinite constraints.


#3

For completeness’ sake, this question can be solved by using Madeleine Udell’s wonderful answer here elsewhere on these forums: