# Nuclear norm as minimum of Frobenius norm product

Nuclear, or trace, or Ky Fan, norm of a matrix is defined as the sum of the singular values of the matrix.

It is claimed that $$\|X\|_\sigma = \min_{UV^T=X} \|U\|\|V\| = \min_{UV^T=X} \frac{1}{2}(\|U\|^2 + \|V\|^2)$$ where $\|\cdot\|_\sigma$ is the nuclear norm of $X$ and $\|\cdot\|$ is the Frobenius norm.

What is the proof?

• What is the relation between $V$ and $V'$? – Tobias Fritz Apr 16 '18 at 8:41
• @TobiasFritz: It is the transpose of each other. But it is irrelevant. I have removed the $'$ or transpose in the question. – Hans Apr 16 '18 at 8:59
• here's a link to a simple (brute-force calculus) derivation: qwone.com/~jason/writing/traceEquivalence.pdf -- there are other more direct ways of showing this too... – Suvrit Apr 16 '18 at 12:39
• @Suvrit: Thank you for the link. However, that note only considers the case for factorization of diagonal matrix multiplication of the singular value decomposition rather than the general case. I have proved the general case below using Von Neumann's trace inequality. Please review. – Hans Apr 16 '18 at 19:04

Here's a nice to way to go about this. I will write $\|\cdot\|_1$ for the nuclear norm, and $\|\cdot\|_2$ for the Frobenius norm.

First, we have the matrix Hölder inequality, which implies $\|UV\|_1\leq\|U\|_2\|V\|_2$. We also have $\|U\|_2\|V\|_2 \leq \tfrac{1}{2}(\|U\|_2^2 + \|V\|_2^2)$. Taken together, these give $$\|X\|_1 \leq \min_{UV = X} \|U\|_2 \|V\|_2 \leq \min_{UV = X} \tfrac{1}{2}(\|U\|_2^2 + \|V\|_2^2).$$ To see that both inequalities are tight, let $X = S(X^*X)^{1/2}$ be the polar decomposition of $X$, with a partial isometry $S$ such that $S^*S$ is the support projection of $X^*X$. Taking $U = S(X^*X)^{1/4}$ and $V = (X^*X)^{1/4}$ works, since $$\|S(X^*X)^{1/4}\|_2^2 = \|(X^*X)^{1/4}\|_2^2 = \mathrm{tr}((X^*X)^{1/2}) = \|X\|_1,$$ where the first step also uses that $S^*S$ is the support projection of $X^*X$.

One of the advantages of this more abstract argument over a brute-force calculation is that this argument also applies in any von Neumann algebras equipped with a normal semifinite trace. Therefore the equations are still valid in that context.

• Nice proof and reference. +1. Please check out my different proof approach as well. – Hans Apr 16 '18 at 19:55
• Your reference about the matrix Hölder inequality is incorrect. Neither this MO question nor the answers contain it. – Denis Serre Apr 18 '18 at 6:49
• @DenisSerre: it's a special case of the "Another generalization..." in the accepted answer that I've linked to. (Take the unitarily invariant norm to be the trace norm.) If you know of a more explicit reference, I'll be happy to include it in my answer. – Tobias Fritz Apr 18 '18 at 7:42
• Not sure if it's any better, but the link now goes to Wikipedia. If there are any actual problems with the answer that lead to a downvote, then it would be good to know what they are. – Tobias Fritz Apr 18 '18 at 9:51

We establish the following manifestation of the Cauchy-Schwartz inequality. \begin{align} \text{tr}(CD)&=\sum_{ij}C_{ij}D_{ji} \\ &\le\Big(\sum_{ij}C_{ij}^2\Big)^\frac12\Big(\sum_{ij}D_{ij}^2\Big)^\frac12 \\ &=\big(\text{tr}(C^TC)\big)^\frac12\big(\text{tr}(D^TD)\big)^\frac12=\|C\|\|D\|, \end{align} for any real square matrices $C$ and $D$.

Perform the singular value decomposition of $X=ASB^T$ where $S$ is the diagonal matrix of the singular values of $X$ and $A$ and $B$ are the associated orthogonal matrices. Apply the above proposition, we have $$\|X\|_\sigma = \text{tr}(S) = \text{tr}(A^TUV^TB)\le \|A^TU\|\|V^TB\|=\|U\|\|V\|\le \frac12(\|U\|^2+\|V\|^2).$$

The equalities are achieved when $U=A\sqrt S$ and $V=B\sqrt S$.

We obtain the desired result.

• That's essentially the same as my answer. Why do you repost it? – Tobias Fritz Apr 16 '18 at 19:05
• @TobiasFritz: You have a wrong assumption. I was close to finishing mine when you posted yours. Also, I am using Von Neumann's trace inequality, while I do not know whether or not the matrix Holder inequality you cited is the same as Von Neumann's trace inequality. – Hans Apr 16 '18 at 19:33
• @TobiasFritz: To give a definitive statement to the second sentence of my last comment, I just checked the source of the matrix Holder inequality and found it to be very much different from the Von Neumann's trace inequality. So our approaches are distinct, and thus one is not a repost of another at all. – Hans Apr 16 '18 at 19:54
• I'm not sure I agree, because your argument uses the trace inequality only to derive the $p=q=2$ case of the matrix Hölder inequality, which is precisely your $\|UV^T\|_\sigma \leq \|U\|\, \|V\|$. – Tobias Fritz Apr 16 '18 at 20:53
• @Hans. Your answer is wrong, because you start from a false identity. The trace of $\sqrt{VU^TUV^T}$ is not equal to that of $\sqrt{U^TU}\,\sqrt{V^TV}$ in general, it is only larger. Your mistake comes from the fact that square root does not behave well under product. Consider the case where $V=D>0$ is diagonal and set $S=\sqrt{U^TU}$. Then $A:=SD$ is diagonalisable with real eigenvalues and arbitrary otherwise. You are comparing the traces of $\sqrt{A^TA}$ and that of $A$. The first one is obviously larger. – Denis Serre Apr 18 '18 at 6:37