(线性代数) – 对角化、对称、 正交、二次型、SVD、PCA

对角化

可以为计算方阵的幂提供方便:

$$
A^k=\begin{bmatrix}
a^k & 0 \\
0 & b^k
\end{bmatrix}
$$

让$A=PDP^{-1}$那么幂次运算:$A^k=(PDP^{-1})\cdots(PDP^{-1})$去掉括号就成了$A^k=PD^kP^{-1}$.

定理1: P320 假设nxn方阵A可对角化, 当且仅当A有n个线性独立的特征向量;这n个特征向量对应的特征值构成D的对角元素, 其对应的特征向量构成P. 这里隐含了: A可逆一定有n个不同的特征向量. 证明的核心就是$AP=PD$.

定理2: P323 充分条件: 有n个不同的的特征值, A是可对角化的

定理3: P324(当A的特征值小于n的情况)

正交

两个向量$\boldsymbol{u}$和$\boldsymbol{v}$的内积有如P376中描述的性质. 如果$\boldsymbol{u}$和$\boldsymbol{v}$正交, 他们的内积$\boldsymbol{u}\cdot\boldsymbol{v}=0$.

正交补(orthogonal complement)就是一个与$\mathbb{R}^n$的子平面$W$中所有向量正交的向量$\boldsymbol{z}$, 记为$W^\perp$.

列空间$\text{Col}A$是正交于零空间$\text{Nul}A$, 因为$\text{Nul}A$的定义为所有的$\boldsymbol{x}$, 满足$A\boldsymbol{x}=\boldsymbol{0}$.

量$\boldsymbol{u}$和$\boldsymbol{v}$的内积: $\boldsymbol{u}\cdot\boldsymbol{v}=\vert\vert\boldsymbol{u}\vert\vert\;\vert\vert\boldsymbol{v}\vert\vert\cos\theta$ 这个和余弦定理类似

定理:P384 假设集合$S=\{\boldsymbol{u_1},\cdots,\boldsymbol{u_p}\}$是$\mathbb{R}^n$中的非0正交向量, 则$S$线性独立且张成一个子空间.

正交基S中的向量$\boldsymbol{y}=c_1\boldsymbol{u_1}+c_2\boldsymbol{u_2}+\cdots c_p\boldsymbol{u_p}$ 的坐标$c_i$:

$$
c_i=\frac{\boldsymbol{y}\cdot\boldsymbol{u_i}}{\boldsymbol{u_i}\cdot\boldsymbol{u_i}}
$$

正交投影

向量$\boldsymbol{\hat{y}}$是$\boldsymbol{u}$方向上的某个向量即$\boldsymbol{\hat{y}}=\alpha\boldsymbol{u}$, z是与u正交的某个向量, 那么y按照向量加法可以分解为

$$
\boldsymbol{y}=\boldsymbol{\hat{y}}+z
$$

$0=\boldsymbol{z}\cdot\boldsymbol{u}=(\boldsymbol{y}-\alpha\boldsymbol{u})\cdot\boldsymbol{u}=\boldsymbol{y}\cdot\boldsymbol{u}-\alpha\boldsymbol{u}\cdot\boldsymbol{u}$

因此$\alpha=\frac{\boldsymbol{y}\cdot\boldsymbol{u}}{\boldsymbol{u}\cdot\boldsymbol{u}}$. $\boldsymbol{\hat{y}}$就是y在u上的正交投影, z就是这个投影的分量.

P395&P399 如果平面$\mathbb{R}^n$的子平面$W$的正交基$\{u_1,u_2,\cdots,u_p\}$, $\hat{y}$在$W$, z在$W^\perp$, 则$y=\hat{y}+z$可以正交分解为: $\hat{y}=\frac{y\cdot u_1}{u_1\cdot u_1}u_1+\cdots+\frac{y\cdot u_p}{u_p\cdot u_p}u_p$. 若基单位正交, 则$u_i\cdot u_i=1$, 令$U=[u_1,\cdots,u_p]$, $\text{proj}_Wy=(y_1\cdot u_1)u_1+\cdots+(y_p\cdot u_p)u_p=UU^Ty,\forall y\in\mathbb{R}^n$也就是$y$是关于U的列向量关于$y_i\cdot u_i$线性组合.

正交矩阵

正交矩阵的列向量之间两两正交, 且其模为1. 这个好处就是一个mxn的矩阵

$$
U^TU=\begin{bmatrix}
\boldsymbol{u_1}^T \\ \boldsymbol{u_2}^T \\ \vdots \\\boldsymbol{u_m}^T
\end{bmatrix}\cdot\begin{bmatrix}
\boldsymbol{u_1} & \boldsymbol{u_2} & \cdots & \boldsymbol{u_m}
\end{bmatrix}
$$

的对角线$\boldsymbol{u_i}^T\boldsymbol{u_i}$为1其余为0. 故而$U^{-1}=U^T$. 且$U^TU=UU^T=I$. 在复数上U称为幺正矩阵(酉矩阵, unitary). Givens矩阵就是一个正交矩阵. 正交矩阵有特点: 这个变换不改变原来向量的正交性长度(内积, 范数): 假设变换$\boldsymbol{x}\mapsto U\boldsymbol{x}$, $(U\boldsymbol{x})\cdot(U\boldsymbol{y})=\boldsymbol{x}\cdot \boldsymbol{y}$, $\vert\vert U\boldsymbol{x}\vert\vert=\vert\vert \boldsymbol{x}\vert\vert$

对角化和二次型

对称矩阵的对角化

定理1: P450 页指出如果$A$是对称矩阵, 那么任何两个来自不同特征空间的特征向量是正交的. 特征空间就是$(A-\lambda I)=0$的所有结解构成的空间, 也就是$A-\lambda I$的零空间.

定理2: 当且仅当A是对称矩阵($P=P^T$), A可以正交($P=P^{-1}$)对角化: $A^T=(PDP^{-1})^T=(P^{-1})^TD^TP^T=P^TD^TP^T=PDP^{-1}=A$

P452 对称矩阵的谱定理, 可以引出舒尔(Schur)分解. 谱分解

二次型

P456. 在$\mathbb{R}^n$中, $Q(x)=\boldsymbol{x}^TA\boldsymbol{x}$, $A$为二次型矩阵. 假设一个$\mathbb{R}^3$的$\boldsymbol{x}$: $Q(x)={\color{red}{5}}x_1^2+{\color{green}{4}}x_2^2+{\color{blue}{3}}x_3^2{\color{orange}{-1}}x_1x_2+{\color{brown}{8}}x_2x_3$可以写为:

$$
Q(x)=\boldsymbol{x}^TA\boldsymbol{x}=[x_1,x_2,x_3]\begin{bmatrix}
\color{red}{5} & {\color{orange}{-1/2}} & 0 \\
{\color{orange}{-1/2}}&\color{green}{4} & {\color{brown}{4}}\\
0&{\color{brown}{4}}&\color{blue}{3}
\end{bmatrix}\begin{bmatrix}
x_1\\x_2\\x_3
\end{bmatrix}
$$

交叉项就是$x_ix_j$的系数就是第i行/列与第j列/行的对应位置的两倍.

P458(Principle Axes 定理) 假设$\boldsymbol{x}=P\boldsymbol{y}$, $\boldsymbol{x}^TA\boldsymbol{x}=(Py)^TAPy=y^T(P^TAP)y$, 假设A可以正交对角化, 则$A=PDP^{-1}\;\text{存在}D=P^{-1}AP=P^TAP$, 则x中的交叉项全部可以变成用y表示的无交叉项的表示!

二次型可以表述几个常用的圆锥曲线, Principle Axes 在 P459 页有说明.

有约束的优化

P465 如果A是对称矩阵, 定义$m=\min\{\boldsymbol{x}^TA\boldsymbol{x}:||\boldsymbol{x}||=1\}$和$M=\max\{\boldsymbol{x}^TA\boldsymbol{x}:||\boldsymbol{x}||=1\}$, 那么x是M对应的单位特征向量$u_1$时, $x^TAx$的值为M;x是m对应的单位特征向量$u_2$时, $\boldsymbol{x}^TA\boldsymbol{x}$的值为m

P468 A为对称的nxn矩阵, 并可以正交对角化$A=PDP^{-1}$, 如果$D$的主对角线为特征值$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$且P的列向量为对应的特征向量$P=[\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_n]$, 则对于$k=2,3,\cdots,n$, $\boldsymbol{x}^TA\boldsymbol{x}$的最大值且满足约束: $\boldsymbol{x}^T\boldsymbol{x}=1, \boldsymbol{x}^T\boldsymbol{u}_1=0,\cdots,\boldsymbol{x}^T\boldsymbol{u}_{k-1}=0$为$\lambda_k$, 且$\boldsymbol{x}=\boldsymbol{u}_k$

SVD

并不是所有的矩阵可以分解为$A=PDP^{-1}$的形式(D为对称矩阵), 但是任何一个mxn的矩阵$A=QDP^{-1}$可能存在. 一个对称矩阵A的特征值的绝对值的度量了A伸展或者收缩的某个向量(对应的特征向量)的量级. 如果$A\boldsymbol{x}=\lambda \boldsymbol{x}$且$\vert\vert \boldsymbol{x}\vert\vert=1$, $\vert\vert A\boldsymbol{x}\vert\vert=\vert\vert\lambda \boldsymbol{x}\vert\vert=\vert\lambda\vert\;\vert\vert \boldsymbol{x}\vert\vert=\vert\lambda\vert$.

假设一个映射$\boldsymbol{x}\mapsto A\boldsymbol{x}$, A为mxn的矩阵, $AA^T$是对称可以正交对角化. 设$\{\boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_n\}$为$\mathbb{R}^n$的组成$A^TA$的标准正交基(满足约束$||\boldsymbol{v}_i||=1$). 对应特征值$\lambda_1,\cdots,\lambda_n$满足:

$$
\begin{aligned}
||A\boldsymbol{v}_i||^2=(A\boldsymbol{v}_i)^T(A\boldsymbol{v}_i)&=\boldsymbol{v}_i^TA^TA\boldsymbol{v}_i\\&=\boldsymbol{v}_i^T(\lambda_i \boldsymbol{v}_i)\\&=\lambda_i
\end{aligned}
$$

从中可知, $A^TA$是半正定的. $A$奇异值是$A^TA$的特征值的平方根, 记为$\sigma_i=\sqrt{\lambda_i}$. 奇异值也就是是$A\boldsymbol{v}_1,A\boldsymbol{v}_2,\cdots,A\boldsymbol{v}_n$的长度

P473 $A^TA$构成的单位正交的特征向量正交基$\{\boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_n\}$, 对应的特征值$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$, 假设$A$有r给非0的奇异值, $\{A\boldsymbol{v}_1,A\boldsymbol{v}_2,\cdots,A\boldsymbol{v}_r\}$ 是$\text{Col}A$的正交基, 秩为$\text{rank}A=r$

假设mxn矩阵:

$$\Sigma=\begin{bmatrix}
D&0\\0&0
\end{bmatrix}
$$

的D是全0部分有m-r行, n-r列. 个别根据上面的定理, $\{A\boldsymbol{v}_1,A\boldsymbol{v}_2,\cdots,A\boldsymbol{v}_r\}$是$\text{Col}A$的正交基, 把他单位化:

$$
\boldsymbol{u}_i=\frac{1}{||A\boldsymbol{v}_i||}A\boldsymbol{v}_i=\frac{1}{\sigma_i}A\boldsymbol{v}_i
$$

得到标准正交基: $\{\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_r\}$, $\sigma \boldsymbol{u}_i=A\boldsymbol{u}_i$.

假设$r$扩展到$\mathbb{R}^m$, 令$U=[\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_m]$, $V=[\boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_m]$. $AV=[A\boldsymbol{v}_1,A\boldsymbol{v}_2,\cdots,A\boldsymbol{v}_r,0,\cdots,0]=[\sigma \boldsymbol{v}_1,\sigma \boldsymbol{v}_2,\cdots,\sigma_m \boldsymbol{v}_r,0,\cdots,0]=U\Sigma$, $D=\text{diag}(\sigma_1,\cdots,\sigma_r)$, 因此:

$$
\begin{aligned}
U\Sigma&=AV\\A&=U\Sigma V^{-1}=U\Sigma V^T
\end{aligned}
$$

设$A$是mxn的矩阵, 存在一个 mxn矩阵$\Sigma$和mxm的矩阵$U$, 其对角元素为奇异值$\sigma_1\ge\sigma_2\ge\cdots>0$, nxn的矩阵$V$:

$$
A=U\Sigma V^T
$$
右奇异矩阵$V$的列向量是$A^TA$对应于D的特征向量, 左奇异$U$的第i个列向量就是$Av_i$的标准化的正交基. 如果非0的$\boldsymbol{v}$不足, 则$U$中列向量需要根据最后一个非0的标准正交基$\boldsymbol{u}_i$, $\boldsymbol{u}_i^Tx=0$的解集进行施密特正交化以词获得一个生成$\mathbb{R}^m$的空间(有m个线性无关的基)

书中(P479)总结了空间之间的关系

SVD和PCA

另一篇关于 PCA 的文章中,解出了$XX^TW=\lambda{W}$,这里的$W$可以认为是$XX^T$特征向量组成的标准正交基,也即是$\lambda_1,\lambda_2,\cdots,\lambda_r$.假设样本: $[X_1,X_2,\cdots,X_N]$为pxN的矩阵, 均值为:

$$
M=\frac{1}{N}(X_1,X_2,\cdots,X_N)
$$

需要把这些样本对齐到中心:

$$
\hat{X_i}=X_i-M
$$

pxN平均偏差/离差矩阵(mean deviation)$B=[\hat{X_1}, \hat{X_2},\cdots,\hat{X_N}]$如果是采样协方差矩阵:

$$
S=\frac{1}{N-1}(BB^T)
$$

PCA

找到一个正交的$p\times p$方阵$P=[\boldsymbol{u}_1,\cdots,\boldsymbol{u}_p]$, 使得:

$$
X=PY
$$

如果简化来看:

$$
[x_1,x_2,\cdots,x_p]^T=[\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_p][y_1,y_2,\cdots,y_p]^T
$$

中的新的变量$Y_i$是对应于B中的$\hat{X_i}$的坐标向量(对于一组基$\{\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_p\}$, $\mathbb{R}^p$中的向量$y$可以写为坐标与基底的和$y=c_1\boldsymbol{u}_1+\cdots+c_p\boldsymbol{u}_p$, P250). $i=1,2,\cdots,N$

P486, 对于任何一个正交矩阵$P$, $Y_1,Y_2,\cdots,Y_N$的协方差矩阵为$P^TSP$: 假设$\boldsymbol{w}\in\mathbb{R}^p$全为1,$[\hat{X_1}\; \hat{X_2}\;\cdots\;\hat{X_N}]\boldsymbol{w}=\hat{X_1}+\hat{X_2}+\cdots+\hat{X_N}=\boldsymbol{0}$, 因为$\sum_i^N\hat{X_i}=\sum_i^NX_i-\sum_I^NM=0$, 替换为$[Y_1\;Y_2\;\cdots\;Y_N]\boldsymbol{w}=[P\hat{X_1}\;P\hat{X_2}\cdots\;P\hat{X_N}]\boldsymbol{w}=\boldsymbol{0}$, 则Y也是离差形式, 由离差形式的定义:

$$
\begin{aligned}
S&=\frac{1}{N-1}([\hat{X_1}\; \hat{X_2}\;\cdots\;\hat{X_N}][\hat{X_1}\; \hat{X_2}\;\cdots\;\hat{X_N}]^T)\\
&=\frac{1}{N-1}(P[Y_1\;Y_2\;\cdots\;Y_N][Y_1\;Y_2\;\cdots\;Y_N]^TP^T)\\
&=P\frac{[Y_1\;Y_2\;\cdots\;Y_N][Y_1\;Y_2\;\cdots\;Y_N]^T}{N-1}P^T
\end{aligned}
$$

因此$[Y_1\;Y_2\;\cdots\;Y_N]$的采样协方差:

$$
S_Y=P^{-1}S{P^T}^{-1}=P^TSP
$$

P需要使得$P^TSP$可以对角化, 联想到特征值分解, 设$D$的对角元素为S的特征值$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_p\ge0$, 由于S是对称矩阵, 因此有对应单位特征向量$[\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_p]$构成$P$. $S=PDP^T$, $P^TSP=D$. $\boldsymbol{u}_1$为第一主成分, 其决定新变量$y_1$. $\boldsymbol{u}_1^T$是$P^T$的第一行, 在$Y=P^TX$中,

$$
y_1=u_1^TX=c_1x_1+c_2x_2+\cdots+c_px_p
$$

$y_1$因此是原来的变量$x_1,\cdots,x_p$的线性组合. 按照实际需求, 可以扩充投影矩阵$W=[\boldsymbol{u}_1^T,\boldsymbol{u}_2^T,\cdots]$

摘自

  1. 《线性代数及其应用, 第三版》

更多阅读

  1. https://www.cnblogs.com/zhusleep/p/9508790.html
  2. 采样协方差为何分母为 n-1
  3. PCA和SVD的联系