4
$\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
    Commented Oct 11, 2016 at 12:21
  • $\begingroup$ @LinAlg Would the equality constraint define the boundary of the spectrahedron defined by the LMI? $\endgroup$ Commented Oct 11, 2016 at 12:25
  • $\begingroup$ Yes. The key here is the formula following "and, thus,". $\endgroup$
    – LinAlg
    Commented Oct 11, 2016 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$ Commented Oct 11, 2016 at 13:10
  • 1
    $\begingroup$ Yes, it is correct and the standard approach to address this using semidefinite programming. $\endgroup$ Commented Oct 11, 2016 at 13:28

2 Answers 2

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
    Commented Oct 12, 2016 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
    Commented Oct 12, 2016 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$
1
  • $\begingroup$ Aren't $u$ and $v$ swapped in your first bullet point? I.e. $\mathrm{trace}(A^TX) = \sum_i \lambda_i \mathrm{trace}(v_i u_i^T X) = \sum_i \lambda_i u_i^T X \, v_i$. $\endgroup$
    – Luca Citi
    Commented Dec 20, 2021 at 1:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .