Lecture 7 Introduction to the Singular Value Decomposition

Lecture 7 Introduction to the Singular Value Decomposition

1. 问题引入和投影矩阵的性质

Goal:对于观测值$X_1,X_2,\cdots ,X_p\in {\mathbb{R}}^n$,找到一个一维子空间(可以理解为一根直线)能”最好的拟合数据”

Solution：

$$\text{ 把每一个 }{X}_i\text{ 投影到 }\overrightarrow{a}\mathrm{上}，Pro{j}_{\overrightarrow{a}}^{X_i},\text{ 投影到让距离 }{d}_i^2=\Vert X_i-Pro{j}_{\overrightarrow{a}}^{X_i}{\Vert }_2^2\mathrm{和}\mathrm{最}\mathrm{小}。$$

复习Projection Matrices：

If $A\in {\mathbb{R}}^{n\times p}$张成的子空间，那么Projection of $X$ onto $span(cols(A))=Pro{j}_{A}X$，如果$A$的每列都是线性无关的，并且有：

$$\begin{array}{}\text{(1)}& Pro{j}_{A}X=A(A^{T}A{)}^{-1}X\end{array}$$

其中，$P_A=A(A^{T}A{)}^{-1}{A}^T$。

还有性质：

1. $$\begin{array}{}\text{(2)}& P_A=P_A^2=P_A{P}_A=P_A^T=P_A^T{P}_A\end{array}$$

2. If $A=\mathit{a}$,

   $$\begin{array}{}\text{(3)}& P_{\mathit{a}}=\mathit{a}({\mathit{a}}^T\mathit{a}{)}^{-1}{\mathit{a}}^T=\frac{\mathit{a}{\mathit{a}}^T}{{\mathit{a}}^T\mathit{a}}\end{array}$$

   因为$({\mathit{a}}^T\mathit{a}{)}^{-1}$是一个标量(可以看详细投影矩阵的证明)。

1. The orthofonal complement of a subspace is the set of all vectors orthogonal to the subspace.

   子空间的正交补 orthofonal complement 是所有正交于子空间的向量的集合(这个子空间是正交子空间)。并且：$A^{T}B=0$（正交）

   (不是这个图的示意，是)如果$A\in {\mathbb{R}}^{n\times r0}$,那么$B\in {\mathbb{R}}^{n\times (n-r)}$。维度上和不变，正交补的维度是其差。

对于任意的$X\in {\mathbb{R}}^n$,能写作：

$$\begin{array}{}\text{(4)}& IX=P_{A}X+P_{B}X=(P_A+P_B)X\Rightarrow I=P_A+P_B\Rightarrow P_B=I-P_A\end{array}$$

正交空间

2. 证明最小距离和、引入奇异向量奇异值

将$P_a$用式3代入，然后相当于做了提取公因子$X_i$ [拓展作单位矩阵 $I{X}_i$ ]，那么$I-\frac{a{a}^T}{a^{T}a}$可以看作投影矩阵$I-P_a$,由式4可得这也是投影矩阵$P_B$,这就是正交补。再写作内积展开式，由性质2公式3可以知道$(I-\frac{a{a}^T}{a^{T}a}{)}^T(I-\frac{a{a}^T}{a^{T}a})=I-\frac{a{a}^T}{a^{T}a}$.

​ 而$X_i^{T}X$是常数跟$a$无关。即只要最大化$\frac{X_{i}a{a}^T{X}_i}{a^{T}a}$.

​ $a^T{X}_i$是标量。

​

$$\begin{array}{}\text{(5)}& \begin{array}{rl}X{X}^T& =\left[\begin{array}{llll}|& |& |& |\\ X_1& X_2& \cdots & X_p\\ |& |& |& |\end{array}\right]\left[\begin{array}{lll}-& X_1^{\mathrm{\top }}& -\\ -& X_2^{\mathrm{\top }}& -\\ -& ⋮& -\\ -& X_p^{\mathrm{\top }}& -\end{array}\right]\\ & =X_1{X}_1^T+X_2{X}_2^T+\cdots +X_p{X}_p^T\\ & =\sum _1^p{X}_i{X}_i^T\end{array}\end{array}$$

​ 用式5矩阵的外积，写作矩阵外积去掉求和，只要求$argma{x}_a(\frac{a^{T}X{X}^{T}a}{a^{T}a})$。

现在定义一些名词：

1. 使得上是取得最大值的向量$\hat{\mathit{a}}$称作$\mathit{X}$的第一个左奇异向量。

2. $\frac{a^{T}X{X}^{T}a}{a^{T}a}={\sigma }_1^2$(这里没用黑粗体懒得写了)的值称作$X$第一个奇异值。

   $$\begin{array}{}\text{(6)}& \begin{array}{rl}\frac{a^{T}X{X}^{T}a}{a^{T}a}& ={\sigma }_1^2\\ & =\Vert X{\Vert }_{op}^2\text{"operator norm"}\\ & =\Vert X{\Vert }_2^2(\mathrm{跟}\mathrm{向}\mathrm{量}2\mathrm{范}\mathrm{数}\mathrm{有}\mathrm{别})\end{array}\end{array}$$

3. 奇异值分解

$U$的列向量是$X$的列向量的正交基。

$\mathrm{\Sigma }$是没有负元素的对角矩阵，${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_p$。

令$U=[U_1,U_2,\cdots ,U_n]$, $U_1$is the best 1d subspace fit to $X_i^{\prime }$s。也是上面式6的解。

令 ${\tilde{X}}_i^{(1)}=X_i-Pro{j}_{U_1}{X}_i$ ，

​

$$U_2=\text{ the best 1d subspace fit to }{\tilde{X}}_i^{\prime }s.$$

若$X_{n\times p}$有秩$r<min(n,p)$。

thin $\mathrm{\Sigma }$。

4. PCA