5
$\begingroup$

Given $\mathrm A \in \mathbb R^{m \times n}$,

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \| \mathrm X \|_2 \leq 1\end{array}$$


Since $\| \mathrm X \|_2 \leq 1$ is equivalent to $\sigma_{\max} (\mathrm X ) \leq 1$, which is equivalent to $\lambda_{\max} (\mathrm X^\top \mathrm X) \leq 1$, we have

$$1 - \lambda_{\max} (\mathrm X^\top \mathrm X) = \lambda_{\min} (\mathrm I_n - \mathrm X^\top \mathrm X)\geq 0$$

and, thus,

$$\mathrm I_n - \mathrm X^\top \mathrm X \succeq \mathrm O_n$$

Using the Schur complement test for positive semidefiniteness, we obtain the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}$$

Hence, we have the following semidefinite program (SDP)

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}\end{array}$$

Is this correct? Any feedback would be highly appreciated. Thank you.

$\endgroup$
8
  • 1
    $\begingroup$ You reformulate an inequality constraint. The equality constraint is not convex and can therefore not be cast as an LMI. $\endgroup$
    – LinAlg
    Oct 11 '16 at 12:21
  • $\begingroup$ @LinAlg Would the equality constraint define the boundary of the spectrahedron defined by the LMI? $\endgroup$ Oct 11 '16 at 12:25
  • $\begingroup$ Yes. The key here is the formula following "and, thus,". $\endgroup$
    – LinAlg
    Oct 11 '16 at 12:30
  • 2
    $\begingroup$ $A=0$ is a nasty case which destroys a claim that it is correct, but the maximum in non-trivial case is attained at the border of the feasible set which means you can replace the equality with an inequality in this simple program $\endgroup$ Oct 11 '16 at 13:10
  • 1
    $\begingroup$ Yes, it is correct and the standard approach to address this using semidefinite programming. $\endgroup$ Oct 11 '16 at 13:28
7
+100
$\begingroup$

This can be computed in closed-form via SVD. Indeed, given a matrix norm $\|.\|$ on $\mathbb C^{n,m}$, there is always a corresponding dual norm (i.e on the dual space $\mathbb C^{m,n}$) given by

$$\|A\|^{D} := \max_{\|X\| \le 1}\langle A, X\rangle_{\text{F}}, $$ where $\langle A, X\rangle_{\text{F}} := \text{trace}(AX^T)$ is the Frobenius / Hilbert-Schmidt inner product. In particular, it's not hard to show that $\|A\|_2^D = \|A\|_* := \sum_{k}\sigma_k(A)$, the nuclear norm of $A$.

$\endgroup$
2
  • 2
    $\begingroup$ Nice answer. Here's a question that asks to show the dual of the spectral norm is the nuclear norm: math.stackexchange.com/questions/1158798/… $\endgroup$
    – littleO
    Oct 12 '16 at 8:25
  • $\begingroup$ Nice pointer. This bails me out of the debt of having to write that part of the solution. Also, the algebra therein contained is really instructive. $\endgroup$
    – dohmatob
    Oct 12 '16 at 8:50
1
$\begingroup$

Let $A=\sum_i \lambda_i u_i v_i^T$ be the SVD of $A$. The nuclear norm of $A$ is by definition the sum of the singular values, $\sum_i \lambda_i$.

  • The fact that the maximum of your optimization problem is at most the nuclear norm of $A$ follows from $$\langle A, X\rangle = trace(A^TX) =\sum_i \lambda_i v_i^T X u_i \le \sum_i \lambda_i $$ by the triangle inequality because $X$ has operator norm at most one, so $|v_i^T X u_i|\le 1$.

  • The fact that $\sum_i \lambda_i$ can be achieved for some matrix $X$ with operator norm at most one follows by taking $X= \sum_i u_iv_i^T$.

$\endgroup$

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.