Prove that $\text{tr}(((A+B)^T(A+B))^{1/2}) \leq \text{tr}((A^TA)^{1/2}) + \text{tr}((B^TB)^{1/2})$

Question

I'm trying to show that the nuclear norm (sum of singular values of the matrix) is actually a valid matrix norm. I know that

$$\sum\limits_{i=1}^n \sigma_i(A) = \text{tr}((A^TA)^{1/2})$$

So now what is left to prove is triangle inequality $$\text{tr}(((A+B)^T(A+B))^{1/2}) \leq \text{tr}((A^TA)^{1/2}) + \text{tr}((B^TB)^{1/2}) \quad \forall A,B\in M_{n\times n}(\mathbf{R})$$

Which is what I'm currently stuck at. Any help would be appreciated.

UPD. What vector norm the matrix norm $\text{tr}((A^TA)^{1/2})$ is associated to?

Answer 1

The quantity $\|A\| = \sqrt{\langle A,A\rangle} = \operatorname{Tr}(A^TA)^{1/2}$ is a norm.

If you agree that $\langle A,B\rangle = \operatorname{Tr}(B^TA)$ is an inner product, then this inner product obeys the Cauchy-Schwarz inequality $|\langle A,B\rangle| \le \|A\|\|B\|$.

Therefore

\begin{align} \|A+B\|^2 &= \langle A+B, A+B\rangle \\ &= \langle A,A\rangle + \langle A,B\rangle + \langle B,A\rangle + \langle B,B\rangle \\ &=\|A\|^2 + 2\langle A,B\rangle + \|B\|^2\\ &\le \|A\|^2 + 2|\langle A,B\rangle| + \|B\|^2\\ &\le \|A\|^2 + 2\|A\|\|B\| + \|B\|^2\\ &= (\|A\| + \|B\|)^2 \end{align} so $\|A+B\| \le \|A\| + \|B\|$.

This matrix norm is not associated with any vector norm because for the identity matrix we have $\|I\| = \sqrt{n}$, and induced norms must satisfy $\|I\| = 1$.

---

The above discussion was for the norm $\|A\|_2 = [\operatorname{Tr}(A^TA)]^{1/2}$. This is about the norm $\|A\|_1 = \operatorname{Tr}[(A^TA)^{1/2}] = \operatorname{Tr}|A|$ where $|A| = (A^TA)^{1/2}$.

Lemma $1$

For any matrix $A$ and two orthonormal bases $E = \{e_1, \ldots, e_n\}$ and $F = \{f_1, \ldots, f_n\}$ we have $$\sum_{i=1}^n \|Ae_i\|^2 = \sum_{i=1}^n \|Af_i\|^2$$ In particular we have $\|A\|_2^2 = \sum_{i=1}^n \|Ae_i\|^2$.

Proof.

$$\sum_{i=1}^n \|Ae_i\|^2 = \sum_{i=1}^n \sum_{j=1}^n |\langle Ae_i, f_j\rangle|^2 = \sum_{i=1}^n \sum_{j=1}^n |\langle e_i, A^Tf_j\rangle|^2 = \sum_{j=1}^n \|A^Tf_j\|^2$$

Applying this to $F$ and $F$ gives $\sum_{j=1}^n \|Af_j\|^2 = \sum_{j=1}^n \|A^Tf_j\|^2$ which completes the proof.

Let $G = \{g_1, \ldots, g_n\}$ be the orthonormal basis in which $A^TA$ diagonalizes with $A^TAg_i = \lambda g_i$. We have $$\|A\|_2^2 = \operatorname{Tr}(A^TA) = \sum_{i=1}^n \lambda_i = \sum_{i=1}^n \langle A^TAg_i, g_i\rangle = \sum_{i=1}^n \|Ag_i\|^2$$

Lemma $2$

For any positive matrix $A$ and two orthonormal bases $E = \{e_1, \ldots, e_n\}$ and $F = \{f_1, \ldots, f_n\}$ we have $$\sum_{i=1}^n \langle Ae_i, e_i\rangle = \sum_{i=1}^n \langle Af_i, f_i\rangle $$ In particular, for any matrix $A$ we have $\|A\|_1 = \sum_{i=1}^n \langle |A|e_i, e_i\rangle = \||A|^{1/2}\|_2^2$.

Proof.

It follows from Lemma $1$:

$$\sum_{i=1}^n \langle Ae_i, e_i\rangle = \sum_{i=1}^n \|A^{1/2}e_i\|^2 = \sum_{i=1}^n \|A^{1/2}f_i\|^2 = \sum_{i=1}^n \langle Af_i, f_i\rangle$$

Let $G = \{g_1, \ldots, g_n\}$ be the orthonormal basis in which $|A|$ diagonalizes with $|A|g_i = \lambda_i g_i$. We have $$\|A\|_1 = \operatorname{Tr}|A| = \sum_{i=1}^n \lambda_i = \sum_{i=1}^n \langle |A|g_i, g_i\rangle = \sum_{i=1}^n \||A|^{1/2}g_i\|^2 = \||A|^{1/2}\|_2^2$$

To prove the triangle inequality for $\|\cdot\|_1$ for the matrices $A$ and $B$, let $A = V|A|$, $B = W|B|$ and $A+B = U|A+B|$ be the respective polar decompositions, with $V,W,U$ unitary.

For any orthonormal basis $\{e_1,\ldots, e_n\}$ we have

\begin{align} \|A+B\|_1 &= \sum_{i=1}^n \langle |A+B|e_i, e_i\rangle\\ &= \sum_{i=1}^n \langle U^*(A+B)e_i, e_i\rangle\\ &= \sum_{i=1}^n \langle (A+B)e_i, Ue_i\rangle\\ &= \sum_{i=1}^n \Big(\langle Ae_i, Ue_i\rangle + \langle Be_i, Ue_i\rangle\Big)\\ &= \sum_{i=1}^n \Big(\langle V|A|e_i, Ue_i\rangle + \langle W|B|e_i, Ue_i\rangle\Big)\\ &= \sum_{i=1}^n \Big(\langle |A|e_i, V^*Ue_i\rangle + \langle |B|e_i, W^*Ue_i\rangle\Big)\\ &= \sum_{i=1}^n \Big(\langle |A|^{1/2}e_i, |A|^{1/2}V^*Ue_i\rangle + \langle |B|^{1/2}e_i, |B|^{1/2}W^*Ue_i\rangle\Big)\\ &\le \left(\sum_{i=1}^n \||A|^{1/2}e_i\|^2\right)^{1/2}\left(\sum_{i=1}^n\||A|^{1/2}V^*Ue_i\|^2\right)^{1/2} + \left(\sum_{i=1}^n \||B|^{1/2}e_i\|^2\right)^{1/2}\left(\sum_{i=1}^n\||B|^{1/2}W^*Ue_i\|^2\right)^{1/2}\\ &= \||A|^{1/2}\|_2^2 + \||B|^{1/2}\|_2^2\\ &= \|A\|_1 + \|B\|_1 \end{align}

Answer 2

By padding the matrices with zeroes, we may assume that they are square. For any real square matrix $X$, let $X=USV^T$ be its singular value decomposition. Since $S$ is a nonnegative diagonal matrix and the diagonal entries of every real orthogonal matrix $W$ are bounded above by $1$, we have $\operatorname{tr}(S)=\max_{W^TW=I}\operatorname{tr}(SW)$. In turn, we have the following characterisation of the nuclear norm: $$ \|X\|:=\operatorname{tr}\left((X^TX)^{1/2}\right) =\operatorname{tr}(S) =\max_{W^TW=I}\operatorname{tr}(SW) =\max_{Q^TQ=I}\operatorname{tr}(XQ). $$ Now the triangle inequality follows directly: $$ \|A+B\| =\max_{Q^TQ=I}\operatorname{tr}\left((A+B)Q\right) \le\max_{Q^TQ=I}\operatorname{tr}\left(AQ\right) +\max_{Q^TQ=I}\operatorname{tr}\left(BQ\right) =\|A\|+\|B\|. $$