# Minimization of Frobenius norm and Schur complement

There is a famous problem here; however, this is not I want to ask (about proximal operator).

Suppose I have an easy optimization problem:

$$\min_Q \|Q-Q_N\|_F$$

where $\|\cdot\|_F$ is the Frobenius norm: $\|X\|_F = (\operatorname{tr}(X^TX))^{\frac{1}{2}}$.

We know we can consider the following:

$$\mathcal{A}(Q,t) = \begin{bmatrix}I & Q-Q_N\\ (Q-Q_N)^T & tI \end{bmatrix}\succeq 0$$

By Schur complement we have the following $$tI-(Q-Q_N)^T(Q-Q_N)\succeq 0$$

If $Q\in \mathbb{R}$, the above becomes $$t-\|Q-Q_N\|^2\geq 0 \Rightarrow t\geq \|Q-Q_N\|^2 \geq 0$$ So the original problem is equivalent to \begin{align} &\min_{t,Q} & &t \\ & s.t. & & \|Q-Q_N\|^2 \geq 0 \end{align} or
\begin{align} &\min_{t,Q} & &t \\ & s.t. & & \mathcal{A}(t,Q)\succeq 0 \end{align} The second formulation is a SDP

My question is: if $Q\in \mathbb{R}^{n\times n}$ how to obtain the above convex optimization problem (minimize over $t$) with $\|\cdot\|^2$ replaced by $\|\cdot\|_F^2$

Is there any method except the vectorization of matrices?

## 1 Answer

Are you asking for the problem

$$\text{minimize trace(X) subj. to . } \begin{bmatrix}I & Q-Q_N\\ (Q-Q_N)^T & X \end{bmatrix}\succeq 0$$

which minimizes the Frobenius norm of $Q-Q_N$?

• So now variables in your optimization is "$X$ and $Q$" and obviously, it is a SDP. Right? – sleeve chen Mar 13 '17 at 19:57
• Yes, that is correct – Johan Löfberg Mar 14 '17 at 18:03
• Can you do something similar for every Schatten p-norm? – Noel Mar 4 at 20:27
• If you mean $(\sum |a_{ij}|_p)^{1/p}$, that's SOCP-representable for rational $p$, but way too complicated for a simple comment. Alternatively, it can be directly represented using the power cone – Johan Löfberg Mar 5 at 6:53
• I have created a question for this: math.stackexchange.com/questions/3140803/… – Noel Mar 9 at 4:56