# K-support norm CVX implementation

#1

I would like to solve a minimization wrt a vector w in R^n of a function F(w) := f(w) + g(w), where f(w) is convex (I can write it in CVX) and g(w) is either (i) the 2-k symmetric gauge function (Bathia - Matrix Analysis 2013) or (ii) the K-support norm (Argyriou, Foygel, Srebro - Sparse prediction with the k-support norm 2012). I am finding difficulties in writing these two norms abiding to the CVX rules. Their definitions are the following:

1. 2-k symmetric gauge norm of a vector w in R^n, given a constant k such that 0 < k <= n:
Let u be the vector containing the coordinate-wise absolute values of w.
The 2-k norm of w given constant k is defined as the square root of the sum of the squared k largest components of u.
Since I can upload just one image I will put a formula in the comment below.

2. k-support norm of a vector w in R^n, given a constant k such that 0 < k <= n:

the arrow pointing downwards after a vector means the same vector with elements in descending order.

Any idea? Thanks

#2

2-k support norm formula:

note that “u” here is “w” in the main post, sorry for the confusion.

(Mark L. Stone) #3

To get you started, the square of the 2-k support norm can be written as `sum_largest(square_abs(x),k)`
and is convex.

I leave the rest to you (or someone else) as an exercise, ha ha.

#4

Thank you for your reply. As sqrt or pow_p with p=0.5 are concave and nondecresing in their argument, they accepts only concave arguments. Is there a way I can take the sqrt of `sum_largest(square_abs(w), k)` still abiding to the DCP rules?

Another question I have is: in order to compute the k-support norm I need to compute `r` via for loops and if statements involving my vector w. How can such features be implemented in CVX?

A Matlab code example to compute such norm can be:

`function norm_w = ksupp_norm(w, k)`

`d = length(w);`
`[beta, ind] = sort(abs(w), 'descend');`
`temp = sum(beta(k:d));`
`found = false;`
`for r=0:k-2`
`if ( (temp >= (r+1) * beta(k-r)) && (temp < (r+1) * beta(k-r-1)) )`
`found = true;`
`break;`
`else`
`temp = temp + beta(k-r-1);`
`end`
`end`
`if (~found)`
`r=k-1;`
`end`

`norm_w = sqrt( beta(1:k-r-1)'* beta(1:k-r-1) + temp^2/(r+1) );`

`end`

(Mark L. Stone) #5

A free virtual beer to whoever can solve this.

Perhaps someone more capable than me can formulate this as a (computationally intensive) solution to an MIDCP. (I’m not saying it can be done) See http://www.jmlr.org/papers/volume17/15-151/15-151.pdf for some relevant math.