Proof of the variational formulation of the nuclear norm

Question

How to show that the nuclear norm can be written in the following way?

$$\|X\|_* = \min\limits_{A,B: AB=X}\frac{\|A\|^2_2}{2} + \frac{\|B\|^2_2}{2}$$

---

Related: Variational characterization of nuclear norm

Answer 1

This is not true. E.g. when $n\ge2$, $$ \|I_n\|_\ast =n >1 =\frac{\|I_n\|_2^2+\|I_n\|_2^2}{2} \ge\min_{AB=I_n}\frac{\|A\|_2^2+\|B\|_2^2}{2} . $$ The correct identity should have Frobenius norms instead of induced $2$-norms on the RHS. Let $U_0SV_0^\ast$ be a singular value decomposition of $X\in M_n(\mathbb C)$. Then $$ \begin{align} \|X\|_\ast &=\|S\|_\ast\\ &=\frac{\|S^{1/2}\|_F^2+\|S^{1/2}\|_F^2}{2}\\ &=\frac{\|U_0S^{1/2}\|_F^2+\|S^{1/2}V_0^\ast\|_F^2}{2}\\ &\ge\inf_{AB=X}\frac{\|A\|_F^2+\|B\|_F^2}{2}\tag{1}\\ &\ge\inf_{AB=X}\|A\|_F\|B\|_F.\tag{2} \end{align} $$ However, for any pair of matrices $(A,B)$ with $AB=X$, we have $$ \begin{aligned} \|A\|_F\|B\|_F &=\max_{U,V\in U(n)}\|A^\ast U\|_F\|BV\|_F\\ &\ge\max_{U,V\in U(n)}|\langle A^\ast U,BV\rangle_F|\\ &=\max_{U,V\in U(n)}|\operatorname{tr}(U^\ast ABV)|\\ &=\max_{U,V\in U(n)}|\operatorname{tr}(U^\ast XV)|\\ &=\|X\|_\ast . \end{aligned} $$ It follows from $(1)$ and $(2)$ that $$ \|X\|_\ast =\inf_{AB=X}\frac{\|A\|_F^2+\|B\|_F^2}{2} =\inf_{AB=X}\|A\|_F\|B\|_F.\tag{3} $$ Two infima in $(3)$ are actually minima and they are attained by $(A,B)=(U_0S^{1/2},\,S^{1/2}V_0^\ast)$.