协方差矩阵与矩阵分解

1 协方差矩阵定义

$$X = [X_1, X_2, .., X_n]^T\\ \mu = [\mu_1, \mu_2, ..., \mu_n]^T\\ \Sigma = E[(X-\mu)(X-\mu)^T]$$

2 协方差矩阵的半正定性质

1. 协方差矩阵为半正定矩阵

证明：

$$\forall \ a \in Vec_{n,1} \and a \not = 0 \\ a^T\Sigma a = a^TE[(X-\mu)(X-\mu)^T]a \\ = E[a^T(X-\mu)(X-\mu)^Ta] \\ = E[((X-\mu)^Ta)^T(X-\mu)^Ta] \\ = E[||(X-\mu)^Ta||^2] \geq 0$$

3 相似对角化

1. 定义：设A为n阶对称矩阵，则必有正交矩阵U，使得 $$A = U\Lambda U^T\\ U^{-1}AU = \Lambda$$

$\Lambda$是对角线上的元素从大到小排列的特征值的对角阵

1. 理论基础：实对称矩阵的特征值为实数，实对称矩阵不同特征值的特征向量相互正交。

2. (题外话) 对于任意方阵，不同特征值之间特征向量线性无关

   • 证明1

   • 设$x_1,x_2,\dots,x_r$是$r$不同特征值, 且线性无关的特征向量

   • 加入一个$x_{r+1}$, 其对应特征值为$\lambda_{r+1}$, 因此对于$(x_1,x_2,\dots,x_r, x_{r+1})$, 若

   $$\sum_{i=1}^{r+1}k_ix_i=0 \label{eq1}$$

   • $\eqref{eq1}$两侧同时左乘$A$， 得到 $$\sum_{i=1}^{r+1}k_iAx_i=\sum_{i=1}^{r+1}k_i\lambda_ix_i=0 \label{eq2}$$

   • $$\eqref{eq1}$$ 两侧同时左乘$\lambda_{r+1}$, 得到 $$\sum_{i=1}^{r+1}k_i\lambda_{r+1}x_i=0 \label{eq3}$$

   • 由$\eqref{eq3}-\eqref{eq2}$, 得 $$\sum_{i=1}^{r+1}k_i(\lambda_{r+1} - \lambda_i)x_i=\sum_{i=1}^r k_i(\lambda_{r+1}-\lambda_i)x_i=0$$

   • 由于$\lambda_{r+1}\neq \lambda_i, i=1,2,\dots,r$, 所以$k_i=0, i=1,2,\dots,r$

   • 由$\eqref {eq1}$, 可得$k_{r+1}x_{r+1}=0 \rightarrow k_{r+1}=0$, 因此$(x_1,x_2,\dots,x_r, x_{r+1})$也线性无关

   • 因此进行数学归纳，可证明不同特征值之间特征向量线性无关

   • 证明2

   • 设$\lambda_i$特征向量的极大无关组为$(x_{i1}, x_{i2},\dots, x_{ia})$, 对于$\lambda_j$来说，若其任意一个特征向量$x_j$与$\lambda_i$特征向量线性相关，等价于$x_j$可由$(x_{i1}, x_{i2},\dots, x_{ia})​$线性表示

     • 这是因为若$x_j​$可由$(x_{i1}, x_{i2},\dots, x_{ia})​$线性表示, 则显然线性相关
     • 若$(x_{i1}, x_{i2},\dots, x_{ia}, x_j)​$线性相关，则$\sum_{j=1}^a k_jx_{ij}+k_{a+1}x_j=0​$存在系数非0解，因此$k_{a+1}​$一定不等于1（否则所有系数都是1），因此$x_j=-\sum_{j=1}^a \frac{k_j}{k_{a+1}}x_{ij}​$, 可线性表示

   • 因此设$x_j=\sum_{j=1}^a k_j x_{ia}​$, 则 $$Ax_j=A\sum_{j=1}^a k_j x_{ia}=\sum_{j=1}^a k_j Ax_{ia} \\ = \sum_{j=1}^a k_j\lambda_i x_{ia}=\lambda_i x_j$$ 这与$\lambda_i \neq \lambda_j$矛盾，证毕

3. 实对称矩阵不同特征值的特征向量相互正交

   • 设两个不同特征值为$\lambda_i, \lambda_j$, 设其对应的特征向量分别是$x_i, x_j$，有 $$\left\{ \begin{matrix} Ax_i=\lambda_i x_i\\ Ax_j=\lambda_j x_j \end{matrix} \right. \\ \rightarrow \left\{ \begin{matrix} x_j^TAx_i=(Ax_j)^Tx_i=\lambda_j x_j^Tx_i\\ x_j^TAx_i=x_j^T\lambda_ix_i=\lambda_ix_j^Tx_i \end{matrix} \right. \\ \rightarrow (\lambda_i-\lambda_j)x_j^Tx_i=0 \\ \rightarrow x_j^Tx_i=0$$ 因此，不同特征值之间特征向量正交

   • 对于同一个特征值，只需要特征向量对极大无关组做

4. 构造： $$如果有s个不同的特征值 \\ S = (\mu_{11},...,\mu_{1k_1},\mu_{21}, ...,\mu_{2k_2},...,\mu_{s1}, ...,\mu_{sk_s}) \\ \Lambda = (\lambda_1, ..., \lambda_1, \lambda_2,...,\lambda_2, \lambda_n,...,\lambda_n)$$

5. 证明： $$AS = (A\mu_{11},...,A\mu_{1k_1},A\mu_{21}, ...,A\mu_{2k_2},...,A\mu_{s1}, ...,A\mu_{sk_s}) \\= (\lambda_1\mu_{11},...,\lambda_1\mu_{1k_1},\lambda_2\mu_{21}, ...,\lambda_2\mu_{2k_2},...,\lambda_s\mu_{s1}, ...,\lambda_s\mu_{sk_s}) \\ =(\mu_{11},...,\mu_{1k_1},\mu_{21}, ...,\mu_{2k_2},...,\mu_{s1}, ...,\mu_{sk_s})diag(\lambda_1,...,\lambda_1,\lambda_2,...,\lambda_2,...,\lambda_s,...,\lambda_s) \\ \longrightarrow A S=S\Lambda \\ \longrightarrow A = S\Lambda S^{-1} \\ 根据施密特正交化，存在U使得S=UD，其中D为对角线均为正数的上三角矩阵,U为正交矩阵。 \\ 所以UD\Lambda(UD)^{-1}=U(D\Lambda D^{-1})U^{-1} \\ =U([\lambda_1C_1, \lambda_1C_2,...,\lambda_sC_n] \left[ \begin{matrix} L_1\\ L_2\\ ...\\ L_n \end{matrix} \right])U^{-1} \\=U(\lambda_1C_1L_1+\lambda_1C_2L_2+...+\lambda_sC_nL_n)U^{-1} \\=U\Lambda U^{-1}$$ 注意，经过施密特正交化的$U$，仍然是由特征向量拼起来的。但是他的特征向量与$S$不同，是通过特征子空间依次施密特正交化得来的。

6. 实际意义

7. $\Sigma x$的意义： $$\Sigma x = U\Lambda U^Tx \\ = U\Lambda \left[ \begin{matrix} \mu_{1}^T\\ \mu_{2}^T\\ ...\\ \mu_{n}^T \end{matrix} \right] [a_1\mu_1+a_2\mu_2+...+a_n\mu_n] \\=U\Lambda \left[ \begin{matrix} a_1\\ a_2\\ ...\\ a_n \end{matrix} \right] =U\left[ \begin{matrix} \lambda_1a_1\\ \lambda_1a_2\\ ...\\ \lambda_sa_n \end{matrix} \right] =(U^T)^{-1}\left[ \begin{matrix} \lambda_1a_1\\ \lambda_1a_2\\ ...\\ \lambda_sa_n \end{matrix} \right]$$ 可以理解为，x在特征向量方向商分别增加$\lambda$倍，也就是在U坐标下单位圆变成椭圆。

8. $x^T\Sigma x$的意义 $$x^T\Sigma x = (U^Tx)^T\Lambda U^Tx \\ = [a_1, a_2,...,a_n]\Lambda \left[ \begin{matrix} a_1\\ a_2\\ ...\\ a_n \end{matrix} \right] \\ =\lambda_1a_1^2+\lambda_1a_2^2 + ... + \lambda_sa_n^2$$ 即为在特征向量正交基下的坐标二次方乘以特征值后求和

4 奇异值分解

1. 定义：相似对角化对矩阵有着较高的要求，它需要被分解的矩阵$A$为实对称矩阵，但是现实中，我们所遇到的问题一般不是实对称矩阵。那么当我们碰到一般性的矩阵，即有一个$m×n$的矩阵A，它是否能被分解成类似的形式。 $$有一个n\times m的实矩阵A，可以分解为:\\ A = U\Sigma V^T\\ 其中U和V是单位正交阵，U称为左奇异矩阵，V称为右奇异矩阵。 \\Σ仅在主对角线上有值，我们称它为奇异值，其它元素均为0。$$

2. 证明：

3. 证明1

$$S=A^TA = U^T\Sigma U\\ U^TSU = \Sigma \\U^TA^TAU=\Sigma \\(AU)(AU)^T=\Sigma\ \\ AU 列正交，AU=V\Sigma，其中V是正交矩阵，\Sigma除了对角线元素其他都是0 \\ \longrightarrow A = VSU^T$$

• 证明2

• 奇异值分解的想法：对任意$A_{m\times n }$的矩阵，能否找到一组正交基使得经过它变换后还是正交基

• 由于$A^TA$ 对称，可以进行特征值分解为 $$A^TA=VDV^T$$

• 因此可以得到一组正交基$V=(v_1,v_2,\dots,v_n)​$, 且有 $$A^TAv_i=\lambda_i v_i\\ (Av_i,Av_j)=(Av_i)^TAv_j \\=v_i^TA^TAv_j \\=v_i^T\lambda_jv_j \\=\lambda_jv_i^Tv_j=0$$

• 因为$Rank(A)=r$, 所以$Rank(AV)=r$, 因此$\{Av_1, Av_2,\dots,Av_n\}$中有$r$个向量可以构成$R^m$正交基的一部分，设为前$r$个并且标准化，而$Av_{r+1}, Av_{r+2},\dots,Av_{n}​$必定都是0向量 $$反证法： 若Av_{r+i}是\{Av_1, Av_2,\dots,Av_r\}线性组合且非0 \\则必有，Av_k\in \{Av_1, Av_2,\dots,Av_r\}, <Av_{r+i},Av_k>!=0, 矛盾$$

• 对$\{Av_1, Av_2,\dots,Av_r\}​$标准化得到$\{u_1, u_2,\dots,u_r\}​$ $$u_i=\frac{Av_i}{\sqrt{<Av_i,Av_i>}}=\frac{1}{\sqrt{\lambda_i}}Av_i,i=1,2,\dots,r\\ \rightarrow Av_i=\sqrt{\lambda_i}u_i=\delta_iu_i$$

• 且$\{u_1, u_2,\dots,u_r\}​$一定是$A​$列空间的一组正交基 $$AV=\{Av_1, Av_2,\dotsm,Av_r,0,\dotsm, 0\}\\ \because Av_i \in S_{col}(A) \and <Av_i,Av_j>=0 \and Rank(AV)=r\\ \therefore \{u_1,u_2,\dotsm,u_r,0,\dots,0\}\\=\{\frac{1}{\sqrt{\lambda_1}}Av_1, \frac{1}{\sqrt{\lambda_2}}Av_2,\dotsm,\frac{1}{\sqrt{\lambda_r}}Av_r,0,\dotsm, 0\} \\是A列空间的一组正交基$$

• 然后对$\{u_1, u_2,\dots,u_r\}​$扩充到$R^m​$的一组标准正交基 $$\{u_1, u_2,\dots,u_r\, u_{r+1},\dots,u_m\}$$

• 因此有 $$AV=A(v_1,v_2,\dots,v_n) \\=(Av_1,Av_2,\dots,Av_r,0,\dots,0) \\=(\delta_1u_1, \delta_2u_2,\dots,\delta_ru_r,0,\dots,0) \\=U\Sigma\\ A=U\Sigma V^T$$

• 这就表明任意的矩阵 $A$ 是可以分解成三个矩阵。$V$ 表示了原始域的标准正交基，$U$ 表示经过 A 变换后的co-domain的标准正交基，$\Sigma$ 表示了 $V$ 中的向量与 $U$ 中相对应向量之间的关系

• 求解方法：

$$AA^T=U\Sigma V^T V \Sigma^T U^T = U\Sigma \Sigma^T U^T \\ A^TA = V\Sigma^TU^TU\Sigma V^T = V\Sigma^T\Sigma V^T$$

​ 由于$AA^T$和$A^TA$都是对称矩阵，此即相似对角化的结果，$U$为$AA^T$的特征向量为列向量的矩阵，$V$为$A^TA$的特征向量为列向量的矩阵，奇异值可以有$A^TA$或者$AA^T$的特征值(因为是正定矩阵，所以特征值非负)开方得到。

1. 意义：奇异值可以被看作成一个矩阵的代表值，或者说，奇异值能够代表这个矩阵的信息。当奇异值越大时，它代表的信息越多。因此，若前面若干个最大的奇异值，就可以基本上还原出数据本身。

2. 分析思想去理解奇异值：

$$有n阶矩阵A，令y=Ax\\ 当x^Tx=1时，x表示了n维正球面上的点。\\ y^TA^{-T}A^{-1}y = 1\\ 即y^TBy = 0。 由于B正定，这表示一个椭球面, 且其完全由该椭球面的n个局部极值点确定。\\ 因为y^Ty = x^TA^TAx\\ \rho_A(x) = \frac{y^Ty}{x^Tx} = \frac{x^TA^TAx}{x^Tx}\\ tr(d\rho) = tr(\frac{d(x^TA^TAx)x^Tx-x^TA^TAxd(x^Tx)}{(x^Tx)^2}) \\ = tr(\frac{(dx^TA^TAx+x^TA^TAdx)x^Tx-x^TA^TAx(dx^Tx+x^Tdx)}{(x^Tx)^2}) \\ = tr(\frac{(A^TAx+A^TAx)}{x^Tx}^Tdx) - tr(\frac{xx^T(A^TAx+A^TAx)}{(x^Tx)^2}^Tdx) \\ = tr(\frac{4A^TAx}{x^Tx}^T dx) \\ \longrightarrow A^TAx=\frac{xx^TA^TAx}{x^Tx} = \frac{x^TA^TAx}{x^Tx} x \\ 可以得知，极值点方向为A^TA的特征向量，大小为A^TA特征值的平方根 \\ 可以知道单位球面有n个向量(v_1, v_2, ..., v_n), 左乘A变成极值点(u_1,u_2,...,u_n) \\A[v_1,v_2,...,v_n] =[u_1,u_2,...,u_n] \left[ \begin{matrix} \lambda_1 & ... & ... \\ ... & ... & ... \\ ... & ... & \lambda_n \\ \end{matrix} \right] \\ 可以证明v是正交(难点) \\ A = U \Sigma V^T代数思想理解奇异值：$$

1. 代数思想理解奇异值：

$$Ax = U\Sigma V^Tx \\ = U\Sigma \left[ \begin{matrix} \mu_{1}^T\\ \mu_{2}^T\\ ...\\ \mu_{n}^T \end{matrix} \right] [a_1\mu_1+a_2\mu_2+...+a_n\mu_n] \\=U\Sigma \left[ \begin{matrix} a_1\\ a_2\\ ...\\ a_n \end{matrix} \right] =U\left[ \begin{matrix} \sigma_1a_1\\ \sigma_2a_2\\ \vdots\\ \sigma_ra_r\\ 0\\ \vdots\\ 0 \end{matrix} \right] =[\alpha_1,\alpha_2,...,\alpha_n]\left[ \begin{matrix} \sigma_1a_1\\ \sigma_2a_2\\ \vdots\\ \sigma_ra_r\\ 0\\ \vdots\\ 0 \end{matrix} \right] = \sigma_1a_1\alpha_1 + .. + \sigma_ra_r\alpha_r$$ 可以看V正交系下的单位圆变换到新的正交系下的椭圆。

1. Thin Svg与矩阵的满秩分解

2. 概念：设矩阵$A_{m\times n}$， 且$Rank(A_{m\times n})=r$, 则$A_{m\times n}$可以分解为 $$A=U_{m\times r}\Sigma_{r \times r}V_{n\times r}^T$$ 其中$U​$和$V​$的每一行都相互正交

3. 证明：

   • 由于$A_{m\times n}$可以经过奇异值分解为 $$A = U_{m\times m} \Sigma_{m\times n} V_{n\times n}^T$$

   • 对$U_{mm}​$进行分块$U_{mm}=((U_{1})_{m\times r}, (U_{2})_{m\times (m-r)})​$

   • 对$V_{nn}​$进行分块$V_{nn}=((V_{1})_{n\times r}, (V_{2})_{n\times (n-r)})​$

   • 由$Rank(A_{m\times n})=Rank(\Sigma_{m\times n})=r$, 所以$\Sigma_{m\times n}$对角线只有前$r$个有值

   • 因此，奇异值分解可以写作 $$A = U_{m\times m} \Sigma_{m\times n} V_{n\times n}^T \\=((U_{1})_{m\times r}, (U_{2})_{m\times (m-r)}) \left(\begin{matrix} \Sigma_{rr} &0\\ 0&0 \end{matrix} \right) \left(\begin{matrix} (V_{1})_{n\times r}^T\\ (V_{2})_{n\times (n-r)}^T \end{matrix} \right) \\=U_1\Sigma_{rr}V_1^T$$

   • 其中$U_1$和$V_1$均分别取$U$和$V$的前$r$列即可

4. 有Thin奇异值分解后结构可以看到，$A$可以被满秩分解为 $$A=(U_1\Sigma_{rr})_{m\times r}(V_1^T)_{r\times n}$$

5. 如何求伪逆

   可以看到$A$的伪逆可以是 $$V_1\Sigma_{rr}^{-1}U_1^T$$

5 协方差矩阵的特征向量和特征值

1. 特征向量和特征值的含义

$$设Y = AX， 其中A是通过伸缩和正交变换得到的，X是不相关的 \\ A = U\Lambda^{\frac{1}{2}} \\ \Sigma_X = E[(X-\mu_X)(X-\mu_X)^T] =D,D为对角阵 \\ \Sigma_Y= E[(Y-\mu_Y)(Y-\mu_Y)^T] \\ = E[(AX-A\mu_X)(AX-A\mu_X)^T] \\ = AE[(X-\mu_X)(X-\mu_X)^T]A^T \\ = ADA^T \\ = U(\Lambda D)U^T$$

​ 由此可见，特征值负责尺度变换，特征向量$U$负责旋转。$\Sigma_Y$的特征向量为$X$样本的变换轴，变化的倍数为$\sqrt{\lambda_i}$, 即从$\sigma_i$变为, $\sqrt{\lambda_i} \sigma_i$。

1. 多元正态分布中的协方差矩阵

2. 在多元正态分布中 $$P(Y) \propto exp(Y^T\Sigma_Y^{-1}Y) \\ = exp(Y^T(U\Lambda^{\frac{1}{2}^{-T}})U\Lambda^{\frac{1}{2}^{-1}}Y) \\ = exp((U\Lambda^{\frac{1}{2}^{-1}}Y)^TU\Lambda^{\frac{1}{2}^{-1}}Y) \\ = exp(X^TX)$$

由此可以得知，一般的多元正态分布是将$Y$变换到$X$不相关的标准多元正态分布