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 ?


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

  • $\begingroup$ Thanks for the reply! It seems the first equation relies on $X$ is a square matrix? What if $X$ is non-square, in general? $\endgroup$ – ignescent Nov 8 '16 at 5:17
  • $\begingroup$ No, whether $X $ is square or not, $ X^*X$ will always be square. $\endgroup$ – Martin Argerami Nov 8 '16 at 5:31
  • $\begingroup$ Huh, I see. Thank you very much! $\endgroup$ – ignescent Nov 8 '16 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.