1
$\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$$

$\endgroup$
5
  • $\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
    May 3 '20 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$ May 3 '20 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
    May 3 '20 at 4:27
  • $\begingroup$ To the best of knowledge, finding a closed form is not possible. The dual of the optimization problem would be a best approximation problem in operator 2-norm, which is not analytically tractable, unless you're OK with suboptimal solutions. See mathoverflow.net/questions/271853/… for a discussion. $\endgroup$
    – DSM
    May 3 '20 at 5:19
  • $\begingroup$ @DSM Thanks a lot for the code! $\endgroup$ May 3 '20 at 20:49
4
$\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.

$\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$ May 3 '20 at 20:46

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.