1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A key concept is that $F^{T}\mbox{diag}(b)F=\sum_{i=1}^{n} b_{i} (F_{i}^{T}F_{i})$. $\endgroup$ – Brian Borchers Jan 16 at 16:24
  • $\begingroup$ @BrianBorchers could you please elaborate a bit? $\endgroup$ – abina shr Jan 17 at 12:44
  • $\begingroup$ Take a look at this. $\endgroup$ – Rodrigo de Azevedo Jan 19 at 8:47
  • $\begingroup$ @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? $\endgroup$ – abina shr Jan 21 at 10:54
  • $\begingroup$ @abinashr Don't you have an SDP in $x$ and $b$ already? Next step would be to solve it. $\endgroup$ – Rodrigo de Azevedo Jan 21 at 11:10
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – abina shr Jan 17 at 16:39
  • $\begingroup$ Shouldn't it be $\begin{bmatrix} yI & X \\ X^T & yI \end{bmatrix} \succeq 0$? $\endgroup$ – Rodrigo de Azevedo Jan 19 at 8:45
  • $\begingroup$ yes, thanks Rodrigo! $\endgroup$ – Michael Grant Jan 19 at 13:37
  • $\begingroup$ @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. $\endgroup$ – Michael Grant Jan 20 at 0:43
  • $\begingroup$ @MichaelGrant could you please explain why can't I write it in the more compact form if $b$ is complex? $\endgroup$ – abina shr Jan 21 at 10:45

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.