线性代数|机器学习-P7SVD奇异值分解_svd求解线性方程

1. 奇异值分解

现在我们用的是一个m行n列的矩阵A，那么我们计算下特征值方程：
A m × n x n × 1 = λ x n × 1 ; b m × 1 = A m × n x n × 1

$$\begin{equation} A_{m\times n}x_{n\times 1}=\lambda x_{n\times 1};b_{m\times 1}=A_{m\times n}x_{n\times 1} \end{equation}$$ Am×n​xn×1​=λxn×1​;bm×1​=Am×n​xn×1​​​

• 当 $m\ne n$时，$b_{m\times 1}\ne \lambda x_{n\times 1}$,所以当A为长方形矩阵的时候，由于向量大小的原因，我们无法使用$Ax=\lambda x$公式，为了解决如下问题，我们引入奇异值分解SVD。
  $$\begin{array}{c}{A}_{m\times n}=U_{m\times m}{\Sigma }_{m\times n}{V}_{n\times n}^T,U{U}^T=I_{m\times m},V{V}^T=I_{n\times n}\end{array}$$

1.1 SVD求解

假设我们有任意矩阵A，可以得到SVD分解，$A=U\Sigma V^T$,那么我们可以构造对称矩阵进行求解；$U{U}^T=I,V{V}^T=I$
A A T = U Σ V T V Σ T U T = U ( Σ Σ T ) U T

$$\begin{equation} AA^T=U\Sigma V^TV\Sigma^TU^T=U(\Sigma\Sigma^T)U^T \end{equation}$$ AAT=UΣVTVΣTUT=U(ΣΣT)UT​​

• 我们可以把$A{A}^T$看作是矩阵A右乘一个矩阵$A^T$,所以可以得到$A{A}^T$为矩阵A的列向量的线性组合，所以得到的U肯定在A的列向量空间中。这样可以得到$U,\Sigma$
  $$\begin{array}{c}{A}^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V^T=V({\Sigma }^T\Sigma )V^T\end{array}$$
• 我们可以把$A^{T}A$看作是矩阵A左乘一个矩阵$A^T$,所以可以得到$A^{T}A$为矩阵A的行向量的线性组合，所以得到的V肯定在A的行向量空间中。这样可以得到$V,\Sigma$
• 最后我们通过验证$Av=\sigma u$来验证 $\sigma$ 的符号。
  -奇异值SVD分解后矩阵向量分布情况如图：
  
• 我们发现，对于矩阵A的分解来说，有部分向量$u_{r+1}\cdots u_m$对于与${\sigma }_{r+1}=\cdots ={\sigma }_n=0$，所以这部分的向量其实是$N(A^T)$零空间向量，所以我们希望更一步进行压缩矩阵，我们本身希望用非零的特征值，具体公式如下：
  $$\begin{array}{c}A{v}_1={\sigma }_1{u}_1,A{v}_2={\sigma }_2{u}_2,\cdots A{v}_r={\sigma }_r{u}_r\end{array}$$
• 整理可得如下：
  $$\begin{array}{c}A\left[\begin{array}{cccc}{v}_1& v_2& \cdots & v_r\\ & & & \\ & row-space& & \end{array}\right]=\left[\begin{array}{cccc}{u}_1& u_2& \cdots & u_r\\ & & & \\ & column-space& & \end{array}\right]\left[\begin{array}{cccc}{\sigma }_1& & & \\ & & & \\ & {\sigma }_2& & \\ & & & \\ & & \ddots & \\ & & & \\ & & & {\sigma }_r\end{array}\right]\to A{V}_r=U_r{\Sigma }_r\end{array}$$

1.2 行基和列基转换

• 这样$A{V}_r=U_r{\Sigma }_r$中的均无零向量和零值了。真神奇的想法！！那么行空间的基向量通过上面公式就可以映射到列空间的基向量上，具体如图所示 ：
  
• 证明当$v_1\perp v_2$,经过$Av=\sigma u$时，$u_1\perp u_2$
  $$\begin{array}{c}{u}_1=\frac{A{v}_1}{{\sigma }_1},u_2=\frac{A{v}_2}{{\sigma }_2},u_1^T{u}_2=(\frac{A{v}_1}{{\sigma }_1}{)}^T\frac{A{v}_2}{{\sigma }_2}=\frac{v_1^T{A}^{T}A{v}_2}{{\sigma }_1{\sigma }_2}\end{array}$$
• 我们之前得到如下结论$A^{T}A{v}_2=v_2{\sigma }_2^2$，代入可得：
  $$\begin{array}{c}{u}_1^T{u}_2=\frac{v_1^T{A}^{T}A{v}_2}{{\sigma }_1{\sigma }_2}=\frac{v_1^T{\sigma }_2^2{v}_2}{{\sigma }_1{\sigma }_2}=\frac{{\sigma }_2{v}_1^T{v}_2}{{\sigma }_1}=0\to u_1\perp u_2\end{array}$$

2. Ax图像表示

假设我们有一个矩阵A，进行分解后得到 $A=U\Sigma V^T$,那么可得：
A x = U Σ V T x

$$\begin{equation} Ax=U\Sigma V^Tx \end{equation}$$ Ax=UΣVTx​​

• step1: $V^{T}x$将图像旋转
• step2: $\Sigma V^{T}x$将图像沿轴拉伸
• step3: $U\Sigma V^{T}x$将图像旋转
• 小结，Ax的本质是将向量的基进行旋转，拉伸，旋转作用
  

3. 极坐标表示

我们希望将任意一个矩阵A分解为一个对称矩阵S和正交矩阵Q的形式，可以进行如下变形：
A = U Σ V T = ( U Σ U T ) ( U V T ) , S = U Σ U T , Q = U V T

$$\begin{equation} A=U\Sigma V^T=(U\Sigma U^T) (UV^T),S=U\Sigma U^T,Q=UV^T \end{equation}$$ A=UΣVT=(UΣUT)(UVT),S=UΣUT,Q=UVT​​

4. 小结

通过SVD奇异值分解可得，我们将任意矩阵分解后，可以挑选出r个重要的非零特征值的矩阵。
A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ r u r v r T , σ 1 ≥ σ 2 ≥ ⋯ ≥ σ r ;

$$\begin{equation} A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ru_rv_r^T,\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r; \end{equation}$$ A=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σr​ur​vrT​,σ1​≥σ2​≥⋯≥σr​;​​

• 所以可得得到矩阵A中最重要的信息在${\sigma }_1{u}_1{v}_1^T+\cdots +{\sigma }_k{u}_k{v}_k^T$上。其他的部分因为${\sigma }_{k+1}{u}_{k+1}{v}_{k+1}^T+\cdots +{\sigma }_r{u}_r{v}_r^T$中的$\sigma$太小而可以忽略，这样就起到以小的矩阵组合来表示原始矩阵的方式，这个就是我们的 主成分分析PCA，真神奇！！！