奇异值分解（Singular Value Decomposition）

奇异值分解

为方便讨论所有矩阵都考虑在实数域范围内（复数域的情况可以做相应的替换，如： $A^T\rightarrow A^H$ ，正交矩阵(Orthogonal Matrix) $\rightarrow$ 酉矩阵(Unitary Matrix)）

引理：

设 $m\times n$ 矩阵 $A$ 秩为 $r$ ，则 $AA^T$ 与 $A^TA$ 的所有非零特征值完全相同且非零特征值的个数均为 $r$

$rank(A)=rank(AA^T)=rank(A^TA)=r$

设 $m\times n$ 矩阵 $A$ 和 $n\times m$ 矩阵 $B$ ，则 $AB$ ， $BA$ 具有相同的非零特征值，且非零特征值的代数重数相同

现有一个 $m\times n$ 矩阵 $A$ ，假设它的秩 $rank\left( A \right) =r\le min(m,n)$ ，则 $A$ 可分解为

$A_{m\times n}=U_{m\times m}\varSigma _{m\times n}V^T_{n\times n}$

其中 $U,V$ 是正交矩阵（归一化后就是单位正交矩阵(Orthonormal Matrix)）

$U_{m\times m}=\left[ \begin{matrix} u_1& u_2& \cdots& u_r& \cdots& u_m\\ \end{matrix} \right]$

$\varSigma _{m\times n}=\left[ \begin{matrix} \sigma _1& 0& \cdots& 0& \cdots& 0\\ 0& \sigma _2& \cdots& 0& \cdots& 0\\ \vdots& \vdots& \ddots& \vdots& \ddots& \vdots\\ 0& 0& \cdots& \sigma _r& \cdots& 0\\ \vdots& \vdots& \ddots& \vdots& \ddots& \vdots\\ 0& 0& \cdots& 0& \cdots& 0\\ \end{matrix} \right] =\left[ \begin{matrix} \varSigma _r& O\\ O& O\\ \end{matrix} \right]$

$V_{n\times n}^{T}=\left[ \begin{array}{c} v_1^T\\ v_2^T\\ \vdots\\ v_r^T\\ \vdots\\ v_n^T\\ \end{array} \right]$

$u,v$ 均为列向量

$u$ 叫左奇异值向量(Left Singular vectors)是 $AA^T$ 的单位特征向量

$\begin{matrix} u_1& u_2& \cdots& u_r\\ \end{matrix}$ 是 $C(A)$ 的一组标准正交基

$\begin{matrix} u_{r+1}& u_{r+2}& \cdots& u_m\\ \end{matrix}$ 是 $N(A^T)$ 的一组标准正交基
$v$ 叫右奇异值向量(Right Singular vectors)是 $A^TA$ 的单位特征向量

$\begin{matrix} v_1& v_2& \cdots& v_r\\ \end{matrix}$ 是 $C(A^T)$ 的一组标准正交基

$\begin{matrix} v_{r+1}& v_{r+2}& \cdots& v_n\\ \end{matrix}$ 是 $N(A)$ 的一组标准正交基

$\sigma_i$ 为奇异值(Singular Value)

设 $m\times n$ 矩阵 $A$ 且 $n<m$ ，矩阵 $A^TA$ 的特征值满足 $\lambda _1\ge \lambda _2\ge \cdot \cdot \cdot \ge \lambda _r>0$ ， $\lambda _{r+1}=\lambda _{r+2}=\cdot \cdot \cdot =\lambda _n=0$ ，称 $\sigma _i=\sqrt{\lambda _i}\ ,\ i=1,\cdot \cdot \cdot ,n$ 为矩阵 $A$ 的奇异值。特别地，称 $\sigma _i\ ,i=1,\cdot \cdot \cdot ,r$ 为矩阵 $A$ 的正奇异值

证明： $\lambda_i>0\ , i=1,\cdot \cdot \cdot,r$ ，且奇异值 $\sigma_i$ 为 $Av_i$ 的模长

$\lambda_i,v_i$ 是矩阵 $A^TA$ 的特征值和特征多项式，则

$A^TAv_i=\lambda _iv_i\ ,i=1,2,\cdot \cdot \cdot ,n$

$\lVert Av_i \rVert ^2=\left( Av_i \right) ^T\left( Av_i \right) =v_i^TA^TAv_i =v_i^T\lambda _iv_i =\lambda _iv_{i}^{T}v_i =\lambda _i\lVert v_i \rVert ^2$

又因为 $v_i$ 为单位向量，模长为1

$\lVert Av_i \rVert ^2=\lambda _i\cdot 1=\lambda _i$

$\lVert Av_i \rVert=\sqrt{\lambda _i}=\sigma_i$

得出奇异值 $\sigma_i$ 为 $Av_i$ 的模长

又因为 $\lVert Av_i \rVert ^2\ge0$ 所以 $\lambda _i\ge0$

并且因为 $rank(A^TA)=rank(A)=r$ ，所以矩阵 $A^TA$ 的非零特征值有 r 个

奇异值分解步骤

比较 $AA^T$ 与 $A^TA$ 阶数的大小，优先考虑计算阶数小的矩阵的特征值
假设 $AA^T$ 阶数小，求解出m个特征值，确定对角阵 $\varSigma_{m\times n}$
计算 $AA^T$ 对应的m个特征向量 $\begin{matrix} \alpha _1& \alpha _2& \cdots& \alpha _r& \cdots& \alpha _m\\ \end{matrix}$ （其中 $\begin{matrix} \alpha _1& \cdots& \alpha _r\\ \end{matrix}$ 是属于 $AA^T$ 的非零特征值的特征向量），将其标准化构成单位正交矩阵 $U$
然后根据 $A=U\varSigma V^T$ ， $V_r=A^TU_r\varSigma_r^{-1}$ 计算出 $V$ 的前 r 列，再扩充为 $R^n$ 的一组标准正交基，构成单位正交矩阵 $V$

奇异值分解的应用

$A_{m\times n}=U_{m\times m}\varSigma _{m\times n}V^T_{n\times n}$

$A=\left[ \begin{matrix} u_1& u_2& \cdots& u_m\\ \end{matrix} \right] \left[ \begin{matrix} \sigma _1& 0& \cdots& 0& \cdots& 0\\ 0& \sigma _2& \cdots& 0& \cdots& 0\\ \vdots& \vdots& \ddots& \vdots& \ddots& \vdots\\ 0& 0& \cdots& \sigma _r& \cdots& 0\\ \vdots& \vdots& \ddots& \vdots& \ddots& \vdots\\ 0& 0& \cdots& 0& \cdots& 0\\ \end{matrix} \right] \left[ \begin{array}{c} v_1^T\\ v_2^T\\ \vdots\\ v_n^T\\ \end{array} \right]$