I know that the dual norm of a matrix can be formulated as a semidefinite program (SDP), i.e., $\|X\|_{2,*}$ is the solution to the following SDP in $Y$:

$$\begin{array}{ll} \text{maximize} & Y^T X\\ \text{subject to} & \begin{bmatrix} I & Y\\ Y^T & I\end{bmatrix} \succeq 0\end{array}$$

If instead of $X$, we have $Z = (I - \phi \phi^T)X$, where $P_s = \phi \phi ^T$ is an orthogonal projection, how can we reformulate our SDP?

\begin{align} \max_{Y,\phi}. \quad Y^TZ \\ s.t. \quad \begin{bmatrix}I & Y\\ Y^T& I \end{bmatrix} \succeq 0 \\ Z = (I - \phi \phi^T)X \\ \phi \succ 0 \end{align}

  • 1
    $\begingroup$ Is $\phi$ a variable? If so you can't express this as an SDP, because it's not convex. $\endgroup$ – Michael Grant Mar 20 at 20:11
  • $\begingroup$ Yes, it is. I was hoping there's a work around perhaps with the schur complement lemma. Thank you for your answer, Michael! $\endgroup$ – Sanjana Vijayshankar Mar 21 at 15:34

Your Answer

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

Browse other questions tagged or ask your own question.