奇异值分解

奇异值分解的定义

奇异值分解（SVD）是对矩阵进行分解，但是不要求被分解的矩阵为方阵。如果我们的矩阵 $A$ 是一个 $m \times n$ 的矩阵，则矩阵 $A$ 的 SVD 为：

A_{m\times n}=U_{m \times m} \Sigma_{m \times n} V^T_{n\times n}

其中， $U,V$ 都是正交矩阵。

奇异值分解的过程

如何构建 $U,V$ 正交矩阵，我们可以研究矩阵 $A^TA$ 的特征值和特征向量。

A^TAv_i=\lambda_iv_i,i=1,2,\cdots,n

注意到 $A^TA$ 是半正定矩阵，所以特征值都是 $\ge0$ ，不妨设 $\lambda_1\cdots\lambda_r >0,\lambda_{r+1}\cdots\lambda_n=0$ 。

考虑到 $(Av_i,Av_j)=v_j^T A^TAv_i$ ，

\pmb{v}_j^T\pmb{A}^T \pmb{A}\pmb{v}_i = \lambda_i \pmb{v}_j^T\pmb{v}_i = \left\{ \begin{aligned} &\lambda_i \quad ,1 \leq i = j \leq r \\ &0 \quad , i \neq j 或 i = j > r \end{aligned} \right.

因此， $Av_1,\cdots,Av_r$ 是正交向量组。而且 $||Av_i||=\sqrt{\lambda_i} (i\le r);0(i>r)$ 。

令 $expand$ 代表标准基扩张。

那么，我们可以知道

\begin{aligned} A(v_1,v_2\cdots,v_r,v_{r+1},\cdots,v_n)&=(\sqrt{\lambda_1}u_1,\sqrt{\lambda_2}u_2,\cdots,\sqrt{\lambda_r}u_r,0,\cdots,0)\\ &=expand(u_1,u_2,\cdots,u_r)\begin{bmatrix}\begin{matrix}\sqrt{\lambda_1} \\ &\sqrt{\lambda_2} \\ && \cdots \\ &&& \sqrt{\lambda_r} \end{matrix} O\\O&O\end{bmatrix}_{m\times n} \end{aligned}

令 $U=expand(u_1,u_2,\cdots,u_r)$ ， $V=(v_1,\cdots,v_n)^T$ 即可。

在实际情况中，根据对称性，我们可以令 $V$ 为 $AA^T$ 对应的正交矩阵，但是，由于正交化的方式不同，会出现正负号的差异，在下面的实例中，我们正负号的方向是正确的，保证了答案的正确性。

奇异值分解的实例

例如，当

A=\begin{bmatrix}0 &1 \\1 &1\\ 1 &0\end{bmatrix}

A^TA=\begin{bmatrix} 1 &1 &0\\ 1 &2 &1\\ 0 &1 &1\\ \end{bmatrix}

得到

U=\begin{bmatrix} -\frac{1}{2}\sqrt{2} &\frac{1}{6}\sqrt{6} &\frac{1}{3}\sqrt{3}\\ 0 &\frac{1}{3}\sqrt{6} &-\frac{1}{3}\sqrt{3}\\ \frac{1}{2}\sqrt{2} &\frac{1}{6}\sqrt{6} &\frac{1}{3}\sqrt{3}\\ \end{bmatrix}

AA^T=\begin{bmatrix} 2 &1\\ 1 &2\\ \end{bmatrix}

对角化形成

\begin{bmatrix} 1 &0 &0\\ 0 &3 &0\\ 0 &0 &0\\ \end{bmatrix}

得到

V=\begin{bmatrix} -\frac{1}{2}\sqrt{2} &\frac{1}{2}\sqrt{2}\\ \frac{1}{2}\sqrt{2} &\frac{1}{2}\sqrt{2}\\ \end{bmatrix}

对角化形成

\begin{bmatrix} 1 &0\\ 0 &3\\ \end{bmatrix}

计算得到 $\Sigma$ ，代表矩阵 $A$ 的 奇异值 $\sigma$ ，在这里可以发现 $\sigma_i=\sqrt{\lambda_i}$ 。

\begin{bmatrix} 1&0\\0&\sqrt{3}\\0&0 \end{bmatrix}

代码如下：

1
2
3

Matrix<poly> U=diagonalize(A*A.transpose());
Matrix<poly> V=diagonalize(A.transpose()*A);
Matrix<poly> Sigma=U.transpose()*A*V.transpose();

输出

U
-1/2\2 1/6\6 1/3\3 
0 1/3\6 -1/3\3 
1/2\2 1/6\6 1/3\3 

Sigma
-1 0 
0 \3 
0 0 

V
-1/2\2 1/2\2 
1/2\2 1/2\2

注意到，除了 $0$ 之外，特征值是相同的，事实上，由于换位公式

可以得到

\lambda^n|\lambda E_m -AA^T|=\lambda^m|\lambda E_n-A^TA|

奇异值的舍去

在很多情况下，矩阵拥有为 $0$ 或者接近 $0$ 的奇异值，这样，我们就可以舍弃这些奇异值，

A_{m\times n}=U_{m\times m}\Sigma_{m\times n}V_{n\times n}\approx U_{m\times k}\Sigma_{k\times k}V_{k\times n}

如：

int k=min(n,m);
for (int i=1;i<=min(n,m);++i){
    if (Sigma[i][i]==0){k=i-1;break;}
}
U.resize(m,k);
Sigma.resize(k,k);
V.resize(k,n);
cout<<U.message("New U")<<endl;
cout<<Sigma.message("New Sigma")<<endl;
cout<<V.message("New V")<<endl;
cout<<(U*Sigma*V).message("SVD")<<endl;

可以得到

New U
-1/2\2 1/6\6 
0 1/3\6 
1/2\2 1/6\6 

New Sigma
-1 0 
0 \3 

New V
-1/2\2 1/2\2 
1/2\2 1/2\2 

SVD
0 1 
1 1 
1 0

和之前的矩阵完全一致，但是矩阵的大小明显减少。

我们还可以正经证明舍去较小特征值对矩阵的影响

根据

A=\begin{bmatrix}u_1&u_2&\cdots&u_m\end{bmatrix} \Sigma \begin{bmatrix}v_1&v_2&\cdots&v_n\end{bmatrix}^T

可以得到：

A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots

由此可见，矩阵 $A$ 被分解为若干重要性不同的秩一矩阵的和，重要性由 $\sigma$ 的大小决定。

更进一步，假设 $\sigma_1 \ge \sigma_2 \ge \cdots$ ，我们还可以证明 $A_k=\sum_{i=1}^k \sigma_i u_iv_i^T$ 是最接近 $A$ 的秩为 $k$ 的矩阵。

实例 1

再举一个例子，分解秩一矩阵

1
2
3

1 -1 1 -1
2 -2 2 -2
3 -3 3 -3

可以先得到

U
1/14\14 -2/5\5 -3/70\70 
1/7\14 1/5\5 -3/35\70 
3/14\14 0 1/14\70 

Sigma
2\14 0 0 0 
0 0 0 0 
0 0 0 0 

V
-1/2 1/2\2 -1/6\6 1/6\3 
1/2 1/2\2 1/6\6 -1/6\3 
-1/2 0 1/3\6 1/6\3 
1/2 0 0 1/2\3

之后，舍弃为 $0$ 的奇异值，得到

New U
1/14\14 
1/7\14 
3/14\14 

New Sigma
2\14 

New V
-1/2 1/2\2 -1/6\6 1/6\3

于是进行了秩一分解。

实例 2

再举一个非常大的矩阵的例子，如：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1
1 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1
1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1
1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1
1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1
1 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 1
1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1

舍弃奇异值 0.23324 后，

对应的奇异值为：

12.3163 0 0 0 0 0 0 0 0 0 
0 3.038 0 0 0 0 0 0 0 0 
0 0 2.46862 0 0 0 0 0 0 0 
0 0 0 2.22437 0 0 0 0 0 0 
0 0 0 0 1.70425 0 0 0 0 0 
0 0 0 0 0 1.12276 0 0 0 0 
0 0 0 0 0 0 0.917349 0 0 0 
0 0 0 0 0 0 0 0.711042 0 0 
0 0 0 0 0 0 0 0 0.554809 0 
0 0 0 0 0 0 0 0 0 0.404302

结果十分接近：

0.998005 0.9883 1.02771 0.998329 0.998329 0.995225 0.997898 0.998005 0.998005 0.988255 0.99743 0.991685 0.999124 1.02562 0.996245 
0.998005 0.9883 1.02771 0.998329 0.998329 0.995225 0.997898 0.998005 0.998005 0.988255 0.99743 0.991685 0.999124 1.02562 0.996245 
1.02541 0.069098 0.863568 0.975168 0.975168 1.02098 0.984965 1.02541 1.02541 1.05895 1.03707 1.06906 0.97899 0.858089 1.04252 
0.994468 -0.0411901 1.10053 0.990322 0.990322 0.9824 0.989601 0.994468 0.994468 0.957513 0.993346 -0.027091 -0.00594873 0.0912267 0.989006 
1.01273 0.0185405 0.975198 -0.0217178 -0.0217178 1.0025 0.984059 1.01273 1.01273 1.0113 0.0194441 0.0271887 0.983002 -0.0339994 0.0202372 
0.977285 -0.0296901 0.0350708 0.0407024 0.0407024 -0.00276809 1.03021 0.977285 0.977285 0.983683 -0.0348745 0.953054 1.03169 1.05284 -0.0358809 
1.01972 0.0281142 -0.036783 0.966015 0.966015 0.00356912 -0.0250048 1.01972 1.01972 0.0168181 0.0301485 1.04183 0.973431 0.948729 1.0313 
0.967623 -0.0372832 0.0363475 1.06092 1.06092 0.998565 0.0456977 0.967623 0.967623 -0.0175456 0.950018 0.935407 1.0472 1.0637 0.949191 
1.0248 0.00899492 0.0251542 0.942043 0.942043 0.991348 -0.0452381 1.0248 1.0248 -0.00874884 1.03935 1.04046 0.955971 0.996351 0.0376229 
0.987338 0.00560383 0.959541 1.03547 1.03547 1.0095 0.0284256 0.987338 0.987338 0.0160293 0.97936 0.984046 1.02658 -0.0216632 -0.0185295 
0.992204 -0.0144827 1.02366 1.01149 1.01149 0.99691 0.00812462 0.992204 0.992204 0.989532 -0.0117368 -0.0180916 0.00914866 0.0280407 0.9874 
1.00472 1.04554 0.886061 1.01425 1.01425 1.0202 1.01431 1.00472 1.00472 1.04804 1.00512 0.0279118 0.00925839 0.898167 1.01007 
0.998005 0.9883 1.02771 0.998329 0.998329 0.995225 0.997898 0.998005 0.998005 0.988255 0.99743 0.991685 0.999124 1.02562 0.996245 
0.998005 0.9883 1.02771 0.998329 0.998329 0.995225 0.997898 0.998005 0.998005 0.988255 0.99743 0.991685 0.999124 1.02562 0.996245 
0.998005 0.9883 1.02771 0.998329 0.998329 0.995225 0.997898 0.998005 0.998005 0.988255 0.99743 0.991685 0.999124 1.02562 0.996245

奇异值分解的几何含义

$V^T$ 是正交变换，不改变度量， $\Sigma$ 变换在各个方向进行了拉伸和压缩， $U$ 也不改变度量。