Suggestion request for a CVX-compatible formulation of \gamma_2 norm

1

The \gamma_2 norm of a real m\times n matrix A is defined as $$\gamma_2(A)=max_{u,v}|A\circ uv^T|_{tr},subject,to,|u|_2=|v|_2=1$$ where \|\|_{tr} is the trace norm of a matrix and \circ is the Hadamard product of two matrices. Lee et al [1] give a SDP formulation of this norm, which is as follows: $$\gamma_2(A)=min ,t$$ $$subject,to,\left( \begin{array}{ccc}
W_1 & A\
A^T & W_2 \\end{array} \right)$$ $$diag(W_1)\leq t$$ $$diag(W_2)\leq t$$
So, I need some help to express this model in a form from which the CVX modelling could be obvious. As my SDP modelling skills became a bit rusty, I find it difficult to do it by myself.

[1] Lee. J, et al, Practical Large-Scale Optimization for Max-Norm Regularization, NIPS 2010

2

Your first “constraint” is missing the specification of being a semidefinite constraint. Here is a link to the paper http://www.eecs.berkeley.edu/~brecht/papers/maxnorm.NIPS10.pdf (section 2).

This is quite straightforward to implement in CVX once you have read the Users’ Guide. I believe the following will do the trick.

cvx_begin
variables t W1(m,m) W2(n,n)
minimize(t)
[W1 A;A' W2] == semidefinite(m+n)
diag(W1) <= t
diag(W2) <= t
cvx_end
3

Thanks for helping me! By reading the DCP ruleset, I concluded that CVX can’t handle the first constraint of my problem, so I tried to convert it to the standard SDP form and this was what troubled me.