---
disqus: ierosodin
---

# The Eckart-Young Theorem

> Organization contact [name= [ierosodin]([e-mail])]
###### 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$
* 
* 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