# Formulation of spectral norm minimization as a semidefinite program

Given a matrix $$F \in \mathbb{C}^{m \times n}$$ such that $$m > n$$ and other (non-symmetric) square matrix $$A$$ of size $$n \times n$$, how can one formulate

$$\arg \min_b \left\|A- {F}^{*} \operatorname{diag} \left( b \right) \, {F} \right\|_{2}$$

where $$b \in \mathbb{C}^m$$ is some vector and $$*$$ denotes the conjugate transpose, as a semidefinite program?

I started as follows. Writing the above problem in epigraph form by introducing a variable $$x$$,

$$\begin{array}{ll} \text{minimize} & x\\ \text{subject to} & \left\|A- {F}^{*} \operatorname{diag} \left( b \right) \, {F} \right\|_{2} \leq x\end{array}$$

which is equivalent to

$$\begin{array}{ll} \text{minimize} & x\\ \text{subject to} & \sigma_{\max}(A- {F}^{*} \operatorname{diag} \left( b \right) \, {F} ) \leq x\end{array}$$

which is equivalent to

$$\begin{array}{ll} \text{minimize} & x\\ \text{subject to} & \lambda_{\max}\big((A- {F}^{*} \operatorname{diag} \left( b \right) \, {F} )^*(A- {F}^{*} \operatorname{diag} \left( b \right) \, {F} ) \big) \leq x^2\end{array}$$

Can anybody tell me how I can proceed with this?

• A key concept is that $F^{T}\mbox{diag}(b)F=\sum_{i=1}^{n} b_{i} (F_{i}^{T}F_{i})$. – Brian Borchers Jan 16 at 16:24
• @BrianBorchers could you please elaborate a bit? – abina shr Jan 17 at 12:44
• Take a look at this. – Rodrigo de Azevedo Jan 19 at 8:47
• @RodrigodeAzevedo So I have reached this step: $\begin{array}{ll} \text{minimize} & x\\ \text{subject to} & \begin{bmatrix} x I & A - F^*\mathop{\textrm{diag}}(b) F \\ A^* - F^*\mathop{\textrm{diag}}(conj(b)) F & x I \end{bmatrix} \succeq 0_{2n}\end{array}$. How do I proceed after this? – abina shr Jan 21 at 10:54
• @abinashr Don't you have an SDP in $x$ and $b$ already? Next step would be to solve it. – Rodrigo de Azevedo Jan 21 at 11:10

There are two ways to approach this. One is to recognize that $$\sigma_\max(X)\leq y \quad\Longleftrightarrow\quad \begin{bmatrix} yI & X \\ X^T & yI \end{bmatrix} \succeq 0$$ So the constraint becomes $$\begin{bmatrix} x I & A - F^T\mathop{\textrm{diag}}(b) F \\ A - F^T\mathop{\textrm{diag}}(b) F & x I \end{bmatrix} \succeq 0$$ Another way is to recognize that, for a symmetric matrix, $$\sigma_\max(X) = \max\{-\lambda_\min(X),\lambda_\max(X)\}$$ And with that, we could do $$-x I \preceq A - F^T\mathop{\textrm{diag}}(b)F \preceq x I$$ The latter will be preferred because a pair of LMIs is more performant than one twice the size.
• For complex case, does it simply become $\begin{bmatrix} x I & A - F^*\mathop{\textrm{diag}}(b) F \\ A^* - F^*\mathop{\textrm{diag}}(conj(b)) F & x I \end{bmatrix} \succeq 0$? – abina shr Jan 17 at 16:39
• Shouldn't it be $\begin{bmatrix} yI & X \\ X^T & yI \end{bmatrix} \succeq 0$? – Rodrigo de Azevedo Jan 19 at 8:45
• @abinashr in the complex case, yes that's fine. But note that if $b$ is not real, you lose Hermitian symmetry, so you can't use the second more compact form. – Michael Grant Jan 20 at 0:43
• @MichaelGrant could you please explain why can't I write it in the more compact form if $b$ is complex? – abina shr Jan 21 at 10:45