SVD分解的原理和应用

Optimization

---

Paper Title: A Singularly Valuable Decomposition: The SVD of a Matrix
Author: Dan Kalman
Date: February 13, 2002

1 Theory

SVD(singular value decomposition)，奇异值分解，对于一个$m ×n$的matrix $A$，始终存在

$$A_{m×n}=U_{m×m} \Sigma_{m×n} V^{T}_{n×n}$$
$U,V$是酉矩阵。其实他的本质形式应该是 $$AV=U\Sigma$$ 写成子项的形式 $$A v_{i}=\sigma_{i} u_{i}$$
其中$\sigma_{i}$称之为奇异值。

对于对称矩阵来说，我们称之为$EVD$分解，,对于任意矩阵来说，我们称之为$SVD$分解。

对$A^TA$做$EVD$分解

$$A^{T} A=V D V^{T}$$
其中，$D=\Sigma_{m×n}^T \Sigma_{m×n}$， $\lambda_{i}$是$A^TA$的特征值，这样就有 $$\sigma_{i}=\sqrt{\lambda_{i}}$$
同理有 $$A A^{T}=U \Sigma \Sigma^{T} U^{T}$$

总结:

• singular value一定是$A^TA$和$AA^T$共同特征值的非零部分的正平方根
• for symmetric matrix，$EVD$和$SVD$结果是一样的；对于一般矩阵，$EVD$求出来的就是奇异值(实数)，$SVD$求出来的是特征值(复数)

2 Method1： 证明$Dy=0$的最优解$y$等于$D^TD$的最小奇异值对应的奇异值向量

矩阵$D^TD$的奇异值分解如下：

$$\mathbf{D}^{\top} \mathbf{D}=\sum_{i=1}^{4} \sigma_{i}^{2} \mathbf{u}_{i} \mathbf{u}_{j}^{\top}$$
回顾我们的原始问题如下：
求解$D_{2n×4}y_{4×1}=0$，这是一个超定方程，本质上求解得到的是一个最小二乘解，使用如下表示：
$$\min _{y} ||Dy||^2 = (Dy)^T(Dy) = y^TD^TDy$$
其中$||y|| = 1$

$y$可以由$D^TD$的奇异值向量线性组合得到，也就是可以表示成如下形式

$$y = \sum_{i=1}^{4} k_iu_i = k_iu_i+v$$
其中 $$v=\sum_{j=1,j\not=i}^{4}k_ju_j$$
$$k_i,k_j \in R$$
容易知道$u_i$和$v$正交。
将$y$代入$y^TD^TDy$得到
$$\min _{y} ||Dy||^2 = (k_iu_i+v)^TD^TD(k_iu_i+v) = k_i^2u_i^TD^TDu_i+ v^TD^TDv + k_iu_i^TD^TDv +k_iv^TD^TDu_i$$

由于$u_i$和$v$正交，所以后两项为0；并且$Du_i = \sigma_iu_i$，带入得到

$$\min _{y} ||Dy||^2 = (k_iu_i+v)^TD^TD(k_iu_i+v) = k_i^2u_i^TD^TDu_i+ v^TD^TDv = k_i^2\sigma_i^2||u_i||^2 + v^TD^TDv >= k_i^2\sigma_i^2||u_i||^2$$
当且仅当$v=0$的时候等号成立。
如果想取得最小值，则$\sigma_i=\sigma_4$,也就是取得最小奇异值的时候，目标函数取得最小值，此时
$$y = k_4u_4+v=k_4u_4$$
由于$||y||=1$,所以$k_4=1$,所以
$$y = u_4$$
证明完毕。

3 Method2: 证明$Dy=0$的最优解$y$等于$D^TD$的最小奇异值对应的奇异值向量

$$D = U\Sigma V^T$$
$$\min _{y} ||Dy|| = ||U\Sigma V^T y||$$

由于正交矩阵（广义来看其实是酉矩阵）的保范性

$||U\Sigma V^T y|| = ||\Sigma V^T y|| = ||\Sigma x||$
其中$x = V^Ty$
所以

$$\min _{y} ||Dy|| = ||\Sigma x||$$
而$\Sigma$是一个对角阵，元素由矩阵$D$的奇异值($\sigma_1>\sigma_2>...>\sigma_k$>0)和0组成，如果要想目标函数取得最小值，则
$$x = [0,...,0,1]^T$$
此时得到目标函数的最优解，对应的$x$取值
$$x = V^Ty = \sigma_{min} = \sigma_k$$
$$y = Vx = [v_1,...,v_k][0,...,1]^T = v_k$$

如果$D$是对称矩阵，那么$U=V$，总之最优解为最小奇异值对应的奇异向量。