1
$\begingroup$

How can one simply see that Ky Fan $k$-norm satisfies the triangle inequality? (The Ky Fan $k$-norm of a matrix is the sum of the $k$ largest singular values of the matrix)

Thanks.

  • 2
    @user4727 Thanks for the edit. Are you aware of the original papers by Ky Fan (~1950)? The reason why it is called the "Ky Fan norm" is because he proved it is a norm first. This might be a good opportunity for some "research"! :)2011-03-21

1 Answers 1

5

For any $k$-plane $U$ in $\mathbb{C}^n$, let $i_U$ be the inclusion of $U$ into $\mathbb{C}^n$ and let $p_U$ be the orthogonal projection of $\mathbb{C}^n$ onto $U$.

Lemma: Let the singular values of $A$ be $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n$. Then $\max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right)= \sigma_1+ \cdots +\sigma_k$, where the max is over all pairs of $k$-planes in $\mathbb{C}^n$.

Proof is left for the reader, using his or her favorite definition of singular values.

Then $\max_{U, V} \ \mathrm{Tr} \left(p_V \circ (A+B) \circ i_U\right) \leq \max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right) + \max_{U, V} \ \mathrm{Tr} \left( p_V \circ B \circ i_U \right)$.