10
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ What is the relation between $V$ and $V'$? $\endgroup$
    – Tobias Fritz
    Commented Apr 16, 2018 at 8:41
  • $\begingroup$ @TobiasFritz: It is the transpose of each other. But it is irrelevant. I have removed the $'$ or transpose in the question. $\endgroup$
    – Hans
    Commented Apr 16, 2018 at 8:59
  • 1
    $\begingroup$ 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... $\endgroup$
    – Suvrit
    Commented Apr 16, 2018 at 12:39
  • $\begingroup$ @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. $\endgroup$
    – Hans
    Commented Apr 16, 2018 at 19:04

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice proof and reference. +1. Please check out my different proof approach as well. $\endgroup$
    – Hans
    Commented Apr 16, 2018 at 19:55
  • $\begingroup$ Your reference about the matrix Hölder inequality is incorrect. Neither this MO question nor the answers contain it. $\endgroup$
    – Denis Serre
    Commented Apr 18, 2018 at 6:49
  • $\begingroup$ @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. $\endgroup$
    – Tobias Fritz
    Commented Apr 18, 2018 at 7:42
  • $\begingroup$ 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. $\endgroup$
    – Tobias Fritz
    Commented Apr 18, 2018 at 9:51
-1
$\begingroup$

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 for any pairs of matrices $(U,V)\ni UV^T=X$ $$ \|X\|_\sigma = \text{tr}(S) = \text{tr}(A^TUV^TB)\le \|A^TU\|\|V^TB\|=\|U\|\|V\|\le \frac12(\|U\|^2+\|V\|^2). $$ The first inequality comes from the Cauchy-Schwarz inequality and the second from the squaring a sum. The equalities are achieved when $U=A\sqrt S$ and $V=B\sqrt S$.

We obtain the desired result.

Improve this answer
$\endgroup$
11
  • 3
    $\begingroup$ That's essentially the same as my answer. Why do you repost it? $\endgroup$
    – Tobias Fritz
    Commented Apr 16, 2018 at 19:05
  • $\begingroup$ @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. $\endgroup$
    – Hans
    Commented Apr 16, 2018 at 19:33
  • $\begingroup$ @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. $\endgroup$
    – Hans
    Commented Apr 16, 2018 at 19:54
  • 1
    $\begingroup$ 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\|$. $\endgroup$
    – Tobias Fritz
    Commented Apr 16, 2018 at 20:53
  • 2
    $\begingroup$ @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. $\endgroup$
    – Denis Serre
    Commented Apr 18, 2018 at 6:37

You must log in to answer this question.

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