# $\arg\max$ in the dual norm of the nuclear norm

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

• Solving the problem with CVXPY, as it is a convex program, should help. Are you looking for a more theoretical treatment of the problem?
– DSM
May 3 '20 at 2:39
• @DSM both actually. I am comfortable with python but I haven't used that library before. Is this is easy to solve using CVXPY? May 3 '20 at 3:30
• 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)
– DSM
May 3 '20 at 4:27
• 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.
– DSM
May 3 '20 at 5:19
• @DSM Thanks a lot for the code! May 3 '20 at 20:49

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