---
# System prepended metadata

title: The Eckart-Young Theorem
tags: [學習筆記, Linear Algebra]

---

---
disqus: ierosodin
---

# The Eckart-Young Theorem

> Organization contact [name= [ierosodin](ierosodin@gmail.com)]
###### tags: `Linear Algebra` `學習筆記`

 * Three kind of norm in matrix
     * Spectral norm
         * ${||A||}_2 = max\frac{||Ax||}{||x||} = \sigma_1$
     * Frobenius norm
         * ${||A||}_F = \sqrt{\sigma_1^2 + \sigma_2^2 + ... + \sigma_r^2}$
         * 因為 $A = \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + ... + \sigma_ru_uv_r^T$, 其 element-wise $l_2$ norm 等於 the vector norm of the singular values of $A$, 等於 trace of $A^TA$
         * ![](https://i.imgur.com/QmcsDk7.png)
     * Nuclear norm
         * ${||A||}_N = \sigma_1 + \sigma_2 + ... + \sigma_r$
     * Example
         * Identity matrix
             * ${||I||}_2 = 1$
             * ${||I||}_F = \sqrt{n}$
             * ${||I||}_N = n$
         * Orthogonal matrix
             * 這裡可以任選一個 orthogonal matrix $Q_1 \Rightarrow Q_1IQ_1^T = I$
             * 則 $Q = (QQ_1)IQ_1^T = U\Sigma V^T \Rightarrow$ $Q$ 與 $I$ 的 norm 相同
     * Norm 只跟 singular values 有關, 因此 $A$ 乘上 orthogonal matrix $Q$ 後($QA$ 與 $AQ$), 其 norm 不變
         * $QA = (QU)\Sigma V^T$
         * $AQ = U\Sigma(Q^TU)^T$
 * Eckart-Young theorem
     * $l_2$ or Spectral norm
         * 對於任意矩陣 $B$, rank of $B \leq k$, $||A - B|| \geq ||A - A_k||$
         * Proof:
             * 挑選一個 $x$ 滿足
                 * $Bx = 0$ ($x$ in the null space of $B$)), dim = n - k
                 * $x = \sum_{i = 1}^{k + 1}c_iv_i$, dim = k + 1
                 * 由於 n - k + k + 1 > n, 比找得到同時符合兩者的 vector $x$
             * $\begin{split}{||(A - B)x||}^2 &= {||Ax||}^2 = x^TA^TAx \\
                 &= (\sum_{i = 1}^{k + 1}c_i\sigma_iu_i)^T(\sum_{i = 1}^{k + 1}c_i\sigma_iu_i) \\
                 &= \sum_{i = 1}^{k + 1}c_i^2\sigma_i^2 \\
                 &\geq \sum_{i = 1}^{k + 1}c_i^2\sigma_{k+1}^2 = {||x||}^2 \sigma_{k+1}^2 \\
                 &\Rightarrow \frac{||(A - B)x||}{||x||} \geq \sigma_{k+1} \\
                 &\Rightarrow ||A - B|| = max\frac{||(A - B)x||}{||x||} \geq \sigma_{k+1} = ||A - A_k||
                 \end{split}$
     * Frobenius norm
         * Proof 1:
             * 因為 ${||A − B||}_F = {||U\Sigma V^T - B||}_F = {||\Sigma − U^TBV||}_F$
             * 假設 $C = U^TBV$
             * $\begin{split}{||\Sigma − C||}_F^2 &= \sum_{i, j}{|\Sigma_{i,j} − C_{i, j}|}^2 \\
                 &= \sum_{i = 1}^k{|\sigma_i - C_{i, i}|}^2 + \sum_{i > k}{|C_{i, i}|}^2 + \sum_{i \neq j}{|C_{i, j}|}^2
                 \end{split}$
             * 其最小值出現在 $\sum_{i > k}{|C_{i, i}|}^2 = \sum_{i \neq j}{|C_{i, j}|}^2 = 0$, 且 $C_{i, i} = \sigma_i \Rightarrow B = A_k$
         * Proof 2:
             * $$
 * PCA