2
$\begingroup$

Given a matrix $X \in \mathbb{R}^{m \times n},$ then the spectral norm is defined by

$$\left \| X\right\| := \max\limits_{i \in \{1, \dots, \min\{m,n\}\} }\sigma_i (X)$$

whereas the nuclear norm is defined by

$$\left \| X \right \|_* := \sum\limits_{i=1}^ {\min\{m,n\}} \sigma_i (X)$$

It is a well-known fact that the dual norm of the spectral norm is the nuclear norm. This implies that

$$\|M\| = \sup_{\|X\|_*\leq 1} \langle M, X \rangle$$

where the inner product is defined by $\langle A, B \rangle := \mathop{\textrm{Tr}}(A^TB)$. Given a matrix $M \in \mathbb{R}^{n \times n},$ how to find a matrix $X^*$ such that the following holds?

$$ X^* \in \arg\sup_{\|X\|_*\leq 1} \langle M, X \rangle$$

Improve this question
$\endgroup$
3
  • $\begingroup$ Solving the problem with CVXPY, as it is a convex program, should help. Are you looking for a more theoretical treatment of the problem? $\endgroup$
    – DSM
    Commented May 3, 2020 at 2:39
  • $\begingroup$ @DSM both actually. I am comfortable with python but I haven't used that library before. Is this is easy to solve using CVXPY? $\endgroup$
    – Santiago Armstrong
    Commented May 3, 2020 at 3:30
  • $\begingroup$ import cvxpy as cvx <newline> import numpy as np <newline> N = 5 <newline> X = cvx.Variable((N,N)) <newline> M = np.random.randn(N,N) <newline> prob = cvx.Problem(cvx.Maximize(cvx.trace((M.T)@X)), [cvx.normNuc(X)<=1]) <newline> prob.solve() <newline> print(prob.status) <newline> print(prob.value) <newline> print(X.value) $\endgroup$
    – DSM
    Commented May 3, 2020 at 4:27

1 Answer 1

Reset to default
5
$\begingroup$

The answer is $X^* = uv^*$ where $u$ and $v$ are the left and right singular vectors of $M$ associated with the largest singular value. If the largest singular value has multiplicity larger than $1$, the argsup is a convex set whose extreme points are the matrices of the form described above.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! You are absolutely right! I will add a proof here in case someone is looking for it in the future: Suppose $X^*=uv^*$ where $u$ and $v$ are the left and right singular vectors of $M$ associated with the largest singular value. To show that $X^*$ attains the optimum, it suffices to show that $\langle M, X^*\rangle = \|M\| = \sigma_{max}$. But this follows from the cyclicity of the trace: $trace(M^*uv^*) = trace(V^*\Sigma U u v^*) = trace(v^*V^*\Sigma U u) = \sigma_{max}$ $\endgroup$
    – Santiago Armstrong
    Commented May 3, 2020 at 20:46

You must log in to answer this question.

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