# Maximize $\langle {\bf A} , {\bf X} \rangle$ subject to $\| {\bf X} \|_* \leq 1$

Given $${\bf A} \in \mathbb R^{m \times n}$$, $$\begin{array}{ll} \text{maximize} & \langle {\bf A} , {\bf X} \rangle\\ \text{subject to} & \| {\bf X} \|_* \leq 1\end{array}$$ where $$\| \cdot \|_*$$ denotes the nuclear norm.

Though I know something about the spectral norm, I know almost nothing about the nuclear norm, dual norms, convex analysis, etc. Since I am utterly unqualified to answer this on my own, I post this question.

Related:

• A direct proof of the duality between the nuclear norm and the spectral norm can be found in the second part of this answer by Michael Grant. Mar 17, 2021 at 6:34

## 2 Answers

I assume that $$\| X \|_*$$ is the nuclear norm of $$X$$. Then the function $$f$$ defined by $$f(A) = \sup_{\| X \|_* \leq 1} \langle A, X \rangle$$ is by definition the dual of the nuclear norm. But a standard result is that the dual of the nuclear norm is the spectral norm. Thus $$f(A) = \sigma_\max(A),$$ the largest singular value of 𝐴.

This is easy to formulate using CVX, wbich will convert it to an SDP. How reliably and quickly it solves depends on the size and numerics of the problem.

cvx_begin
variable X(m,n)
minimize(trace(A'*X))
norm_nuc(A) <= 1
cvx_end

• But, there's an analytical solution because the dual of the nuclear norm is the spectral norm. No need to solve an SDP. Mar 18, 2021 at 15:27