equivalent expressions for trace norm

Question

I understand the trace norm (or nuclear norm) of a matrix $X\in\mathbf{R}^{n\times m}$is usually defined as

$$\|X\|_{tr}=\sum_{i=1}^{\min\{m,n\}}\sigma_i$$ where $\sigma_i$'s are the singular values of $X$.

However, some papers uses an alternative definition: $$\|X\|_{tr}=\min_{X=AB'}\|A\|_{Fro}\|B\|_{Fro}$$ where $X=AB'$ is some arbitrary decomposition of $X$ and $\|*\|_{Fro}$ is the Frobenius norm.

But why are these two definitions equivalent?

As far as I understand, if $X=USV'$ is the SVD of $X$ and if $A=UC, B=VSC^{-1}$ where $C$ is diagonal s.t. $X=AB$, then $C=S^{1/2}$ leads to the minimum of $\|A\|_{Fro}\|B\|_{Fro}$.

However, I don't see how to prove the equivalency when $A,B$ are some arbitrary decomposition (not constraint to the form $A=UC,B=VSC^{-1}$)

Can anyone help me ?

Answer 1

Note that, since $X^*X$ is positive-semidefinite (and square), the square roots of its eigenvalues are the eigenvalues of the square root. Thus $$ \|X\|_{\rm tr}=\sum_j\lambda_j(X^*X)^{1/2}=\sum_j\lambda_j((X^*X)^{1/2})=\sum_j\lambda_j(|X|)=\text{Tr}\,(|X|) $$ (hence the name of the norm). Now, if $X=AB$, then with $AB=W|AB|$ the polar decomposition, \begin{align} \|AB\|_{\rm tr}&=\text{Tr}\,(|AB|)=\text{Tr}\,((W^*A)B)\leq\text{Tr}(A^*WW^*A)^{1/2}\,\text{Tr}\,(B^*B)^{1/2}\\ \ \\ &=\text{Tr}(A^*A)^{1/2}\,\text{Tr}\,(B^*B)^{1/2}=\|A\|_2\,\|B\|_2 \end{align} (where the inequality is due to Cauchy-Schwarz).