pca

pca属于线性降维算法。可以说是在降维算法里最出名的一个算法。
开始详细理解之前，首先，我们来看一下降维的形式化定义：
目标：给定$X={x_{i}}^{n}_{i=1},x_{i}\in R^{d}$，寻找线性映射来将数据映射到$R^{p},p \ll d$

• 如何描述线性映射？

回忆：$f(x)=w_{1}x_{1}+w_{2}x_{2}+…+w_{d}x_{d}$被称作一个线性函数，
写成更加简单的形式：$f(x)=w^{T}x$
f就是一个线性变换，从$R^{d}\rightarrow R^{1}$,是把一个d维的数据映射为一个实数。
思考：如果扩展成从$R^{d}\rightarrow R^{p},1< p \ll d$的线性映射？

$$f_{1}(x) = w_{11}x_{x} + w_{12}x_{2} +...+ w_{1d}x_{d} = w_{1}^{T}x \\ f_{2}(x) = w_{21}x_{x} + w_{22}x_{2} +...+ w_{2d}x_{d} = w_{2}^{T}x \\ ... \\ f_{p}(x) = w_{p1}x_{x} + w_{p2}x_{2} +...+ w_{pd}x_{d} = w_{p}^{T}x \\ \Longrightarrow f:R^{d} \rightarrow R^{p}: x \rightarrow Wx, W \in R^{p \times d}$$

只要同时用p个w向量即可，把这些向量堆叠在一起成为一个$p\times d$矩阵。W矩阵的第i行即为$w_{i}$。所以Wx，矩阵变换代表线性映射，把x从d维空间映射到p为空间。

$$f:R^{d} \rightarrow R^{p}: x \rightarrow Wx, W \in R^{p \times d}$$

我们要求矩阵W满足如下条件：$WW^{T} = I_{p}$(行向量之间orthogonal，正交，得到一个单位矩阵I)，即：

• 不同行的行向量之间互相垂直，即$w_{i}^{T}w_{j}=0,\forall i\neq j$
• W的每一个行向量$w_{i}$是一个单位向量：$w_{i}^{T}w_{i}=1,\forall i \in [p]$

回顾一些基础知识：两个向量u和v内积有：$u^{T}v = |u||v|cos\theta$，这里$|u|cos\theta$是u在v上的投影的长度。
对应到上面x和w的内积，可得:$w^{T}=|w||x|cos\theta$，因为w为单位向量，所以最终得$|x|cos\theta$,即x在w上投影的长度。

$\tilde{x}=Wx \in R^{p}$是x在$W = {w_{1},…,w_{p}}\subseteq R^{d}$扩张的线性子空间中的坐标。

$$y\approx \tilde{x}_{1}w_{1} + \tilde{x}_{2}w_{2} +...+\tilde{x}_{p}w_{p}$$

是对原向量x的一个重构，简洁的表示方法：$y=W^{T}\tilde{x}=W^{T}Wx\in R^{d}$
重点：$\tilde{x}=Wx\in R^{p}$是从$R^{d}$到$R^{p}$的一个投影操作（降维压缩）
重点：$y=W^{T}\tilde{x}=W^{T}Wx\in R^{d}$是用降维后的表示对原始数据的一个重构
更一般地，第一部分被称作dimensionality reduction（encoding），第二部分