1
$\begingroup$

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:

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – user1551
    Mar 17, 2021 at 6:34

2 Answers 2

3
$\begingroup$

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 𝐴.

$\endgroup$
0
0
$\begingroup$

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
$\endgroup$
1
  • 1
    $\begingroup$ But, there's an analytical solution because the dual of the nuclear norm is the spectral norm. No need to solve an SDP. $\endgroup$
    – littleO
    Mar 18, 2021 at 15:27

You must log in to answer this question.

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