5
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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$?

$\endgroup$
5
  • $\begingroup$ So now variables in your optimization is "$X$ and $Q$" and obviously, it is a SDP. Right? $\endgroup$ Mar 13 '17 at 19:57
  • $\begingroup$ Yes, that is correct $\endgroup$ Mar 14 '17 at 18:03
  • $\begingroup$ Can you do something similar for every Schatten p-norm? $\endgroup$
    – Noel
    Mar 4 '19 at 20:27
  • $\begingroup$ 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 $\endgroup$ Mar 5 '19 at 6:53
  • $\begingroup$ I have created a question for this: math.stackexchange.com/questions/3140803/… $\endgroup$
    – Noel
    Mar 9 '19 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.