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

Question

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:

• Show that the dual norm of the spectral norm is the nuclear norm

• Maximize $\langle \mathrm A , \mathrm X \rangle$ subject to $\| \mathrm X \|_2 \leq 1$

Answer 1

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 .

Answer 2

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