SVD分解推导证明
@[toc]
0. 线性代数与矩阵基础知识回顾
本文讨论的范围实数空间，不涉及复数空间，因此各种术语和定理都以实空间下的名称为准，当然也可以推广到复数空间，只需进行一些名词的变换（对称矩阵-Hermitian举矩阵，正交矩阵-酉矩阵）。
0.1. 正交向量组
对于向量$x_1,x_2,\cdots,x_k\in R^n$，若$x_i^Tx_j=0,\forall (i,j)\in \{(i,j)\lvert 1\leq i<j\leq k\}$，则称$x_1,x_2,\cdots,x_k$是一组正交向量组，简称正交组。如果正交组里面的向量还是归一化的，即$x_i^Tx_i=1,i=1,2,\cdots,k$，则称该正交组为标准正交组。
0.2. 正交矩阵
一个实的正方矩阵$Q\in R^{n\times n}$称为正交矩阵，若：
由上述定义可以推出如下几个等价的叙述：
- $Q$是正交矩阵
- $Q^T$是正交矩阵
- $Q$是非奇异的，并且$Q^T=Q^{-1}$
- $QQ^T=Q^TQ=I$
- $Q=[q_1,q_2,\cdots,q_n]$的列组成标准正交组
- $Q$的行组成标准正交组
- $\forall x\in R^n, y=Qx$的Euclidean长度与$x$的Euclidean长度相等，也即有$y^Ty=x^Tx$。
0.3. 正定矩阵
一个对称矩阵$A$称为
- 正定矩阵($A>0$)：若二次型$x^TAx>0,\forall x\neq 0$;
- 半正定矩阵($A\geq 0$)：若二次型$x^TAx\geq 0,\forall x\neq 0$;
- 负定矩阵：如果$-A$是正定的
- 半负定矩阵：如果$-A$是半正定的
正定矩阵的等价条件：
- 存在可逆矩阵$C$使$C^TC$等于该矩阵
- 正定矩阵$<=>$所有特征值取正实数，半正定矩阵$<=>$所有特征值取非负实数
0.4. 特征值
- 对于n阶对称矩阵$A$的特征值都是实数。
- 对于n阶对称矩阵$A$，总存在正交阵$Q$，使得$Q^{-1}AQ$是对角阵，且对角线元素就是$A$的特征值按从大到小排列。即$Q^{-1}AQ=diag(\lambda_1,\lambda_2,\cdots,\lambda_n),\lambda_1>\lambda_2>\cdots>\lambda_n$。
1. 奇异值分解（Singular Value Decomposition）
1.1. svd的数学描述
svd告诉我们，对任意$m\times n$的矩阵$A$，都可以表示为下面这种形式：
其中$U$是$m \times m$的正交阵，$V$是$n\times n$的正交阵，$\Sigma$是$m\times n$的对角阵，
$\Sigma_1=diag(\sigma_1,\sigma_2,\cdots,\sigma_r),r=rank(A)$，其对角元素按照从大到小排列
1.2. svd的证明
在开始证明前，先给出几个引理：
- 引理1：$A^TA$可对角化，且具有实的非负特征值（这是因为$A^TA$是半正定矩阵）
- 引理2：$rank(A)=rank(A^TA)=rank(AA^T)$
- 引理3：$A=0\ \Leftrightarrow\ A^TA=0$
下面开始证明：
设$rank(A)=r$，根据引理1和引理2，存在$n\times n$的正交矩阵$V$，使得
其中$\lambda_1>\lambda_2>\cdots>\lambda_r>0=\lambda_{r+1}=\cdots=\lambda_n$为$A^TA$的n个非负特征根。
令$\Sigma_1=diag(\sigma_1,\sigma_2,\cdots,\sigma_r)=diag(\sqrt\sigma_1,\sqrt\sigma_2,\cdots,\sqrt\sigma_r)$，$V_1=[v_1,v_2,\cdots,v_r]，V_2=[v_{r+1},v_{r+2},\cdots,v_{n}]$，并且有$V=[V_1,V_2]$。
从而有$A^TAV_1=V_1\Sigma_1^2$，进一步得到：
令$U_1=AV_1\Sigma_1^{-1}$，则有$U_1^TU_1=I$。此时，我们可以选择$m-r$组标准正交向量与$U_1$的列向量组成一组标准正交基，也即$U=[U_1,U_2]$是一个m阶正交阵，且$U_1^TU_2=0$。
另一方面，容易得到：
根据引理3可得$AV_2=0$
综上可得：
也即$A=U\Sigma V^T$，到此奇异值分解定理得证。