# Minimization of Frobenius Norm and Schur Complement

There is a famous problem Optimization of Frobenius Norm and Nuclear Norm; 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?

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? Mar 13 '17 at 19:57
• Yes, that is correct Mar 14 '17 at 18:03
• Can you do something similar for every Schatten p-norm?
– Noel
Mar 4 '19 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 Mar 5 '19 at 6:53
• I have created a question for this: math.stackexchange.com/questions/3140803/…
– Noel
Mar 9 '19 at 4:56