奇异值分解（SVD）

SVD(Singular Value Decomposition, 奇异值分解)是线性代数中既优雅又强大的工具, 它揭示了矩阵最本质的变换. 使用SVD对矩阵进行分解, 能得到代表矩阵最本质变化的矩阵元素. 这就好比一个合数能表示为若干质数之积, 分解合数能得到表示该合数的质因数; 复杂周期信号可以表示为若干简单的正弦波和余弦波之和, 使用傅里叶变换能得到表示该信号的简单波; 复杂矩阵所代表的线性变换可由若干个简单矩阵所代表的线性变换组合起来, 使用SVD能找到这些简单矩阵.

一、SVD主要内容

​ SVD叫做奇异值分解，其实意思就是主成分分解，求解奇异值。SVD分解如下：

\begin{align*}\label{1} &A = U \sum{}{}{V^T} ,\quad U是正交矩阵,\quad \sum{}{}是对角矩阵\quad ,V是正交矩阵\\ &U是M * M矩阵,\quad U=AA^T,\quad U是正交矩阵，即满足U^TU=I\\ &\sum{}{}是M * N矩阵,\quad除了主对角线全部为0，\quad主对角线每个元素为奇异值\\ &V^T是N*N矩阵,\quad V^T=A^TA,\quad V^T是正交矩阵，即满足V^TV=I\\ \end{align*}

二、SVD数学含义

矩阵在线性代数系统中是一个核心的概念, 其从不同的角度出发都能拥丰富的内涵. 对于矩阵 , A_{m*n} 当其参与运算时，

Ax = b \tag{1} ​

我们可以从以下三个角度看待其角色：

​ 1、矩阵A是线性方程组的系数组成的矩阵, 其每一行是中每一个方程式的系数部分, 通过分析矩阵的秩rank（A）和其极大线性无关组的情况，对于使用高斯消元法等进行求解也比较方便

​ 2、当 m\geq n且rank（A）=n 时，矩阵A是 R^n 空间中的一个基，在这个基上面，向量 \vec{x}=[x_1,\cdots,x_N]^T ，而此向量在标准正交基上面表示为 \vec{b}=[b_1,\cdots,b_n]^T ，此时隐含一个基变换的关系，即Ax=Ib，I为标准正交基；

​ 3、矩阵A本身表示一个线性变换，上述公式表示其对X进行线性变换得到向量b的过程

​ 上述的关于矩阵的各种角色与我们阐述SVD有什么关系呢? 当我们将矩阵视为一种线性变换时, SVD可以帮我们揭示组成该线性变换的最本质的变换, 具体地, SVD揭示了这样的一个事实:对于任意的矩阵A,我们总能找到一组单位正交基, 使得A对其进行变换之后, 得到的向量组仍然是正交的.这样的表述还是相当地晦涩, 我们不妨在二维平面中举一个例子.

​ 设有矩阵 A , 其对单位正交基 \vec{v_1},\vec{v_2} 进行线性变换，得到的向量仍然是彼此正交的，即 A\vec{v_1},A\vec{v_2} 仍然是正交的，设方向 A\vec{v_1},A\vec{v_2} 上的单位向量是 \sigma_1,\sigma_2 ，则我们可以得到： A\vec{v_1} = \sigma_1\vec{\mu_1}\ \tag{2}

A\vec{v_2} = \sigma_2\vec{\mu_2} \tag{3}

现在利用矩阵A对向量 \vec{x} 进行线性变换.我们先将向量 \vec{x} 在单位正交基 \vec{v_1},\vec{v_2} 进行表示，即

\begin{align} \vec{x}&=[v_1,v_2]\cdot\left[\begin{matrix} v_1^T \ \\v_2^T\end{matrix}\right] \cdot\vec{x}\ \\ &=[v_1,v_2]\cdot\left[\begin{matrix} v_1^T\vec{x} \ \\v_2^T\vec{x}\end{matrix}\right] \tag{4} \end{align}

由(2),(3),(4)我们有

\begin{align} \because A\vec{x} &= A \cdot [v_1,v_2] \cdot \left[\begin{matrix} v_1^T \\\ v_2^T\end{matrix}\right] \cdot \vec{x}\ \\ &=[Av_1,Av_2] \cdot \left[\begin{matrix} v_1^T \ \\v_2^T\end{matrix}\right] \cdot \vec{x}\\\ &=[\sigma_1\mu_1,\sigma_2\mu_2] \cdot \left[\begin{matrix} v_1^T \ \\v_2^T\end{matrix}\right] \cdot \vec{x}\ \\ &=[\mu_1,\mu_2]\cdot \left[ \begin{matrix} \sigma_1 & 0\\\ 0 & \sigma_2\end{matrix} \right] \cdot \left[\begin{matrix} v_1^T \ \\v_2^T\end{matrix} \right] \cdot \vec{x}\\\ &=U\sum{}{}V^T \cdot \vec{x} \tag{5}\ \\ \therefore A&=U\sum{}{}V^T \tag{6} \ \end{align}

至此, 我们由"对于任意的矩阵 A , 我们总能找到一组单位正交基, 使得A对其进行变换之后, 得到的向量组仍然是正交的", 即(2)(3)出发, 得到了矩阵A 最终的分解形式(6). (6)表达了这样一个事实, 对于任意的矩阵A , 我们总可以将其分解为一个正交矩阵 U , 一个对角矩阵 \sum 和另一个正交矩阵的转置 V^T 的乘积, 这便是SVD的核心内容.

三、SVD几何含义

对于任意的矩阵 A, 我们总可以将其分解为一个正定矩阵 U, 一个对角矩阵 \sum 和另一个正定矩阵的转置 V^T 的乘积, 即等式(6)所表述的内容. A=U\sum{}V^T 表示矩阵 A所代表的线性变换可以由更简单的旋转, 拉伸变换进行合成. 这些更简单的变换是怎么进行生效的呢? 我们还是在二维平面中举例说明.

当使用矩阵 A对向量 \vec{x} 进行变化时, 我们可以先将向量 \vec{x} 在单位正交基 \vec{v_1},\vec{v_2} 上进行表示, 即(4)所表述. 我们不妨令 \xi_1=v_1^T\vec{x},\xi_2=v_2^T\vec{x},则\xi_1,\xi_2 是向量 \vec{x} 在单位正交基 \vec{v_1},\vec{v_2} 上的坐标, 即

\begin{align*} \vec{x}&=[v_1,v_2]\cdot\left[\begin{matrix} v_1^T \\ v_2^T\end{matrix}\right] \cdot\vec{x}\\ &=[v_1,v_2]\cdot\left[\begin{matrix} v_1^T\vec{x} \\ v_2^T\vec{x}\end{matrix}\right]\\ &=[v_1,v_2]\cdot\left[\begin{matrix} \xi_1 \\ \xi_2\end{matrix}\right] \tag{7} \end{align*}

由(6),(7)我们有

\begin{align*} A\vec{x}&=U\sum{}{}V^T \cdot \vec{x}\\ &=[\mu_1,\mu_2]\cdot \left[ \begin{matrix} \sigma_1 & 0\\ 0 & \sigma_2\end{matrix} \right] \cdot \left[\begin{matrix} v_1^T \\ v_2^T\end{matrix} \right] \cdot \vec{x}\\ &=[\mu_1,\mu_2]\cdot \left[ \begin{matrix} \sigma_1 & 0\\ 0 & \sigma_2\end{matrix} \right] \cdot \left[\begin{matrix} v_1^T \\ v_2^T\end{matrix} \right] \cdot [v_1,v_2]\cdot \left[\begin{matrix} \xi_1 \\ \xi_2\end{matrix}\right]\tag{8}\\ \end{align*}

现在我们仔细地来分析(8)中各矩阵的具体操作效果

\begin{align*} A\vec{x}&=\underbrace{\underbrace{[\mu_1,\mu_2]}_{\text {旋转}} \underbrace{\cdot \underbrace{\left[ \begin{matrix} \sigma_1 & 0\\ 0 & \sigma_2\end{matrix} \right]}_{\text {拉伸}} \cdot \underbrace{\underbrace{\left[\begin{matrix} v_1^T \\ v_2^T\end{matrix} \right]}_{\text {旋转}} \cdot \underbrace{ \underbrace{[v_1,v_2]}_{\text {单位正交基V}} \underbrace{\cdot \left[\begin{matrix} \xi_1 \\ \xi_2\end{matrix}\right]}_{\text {x在V坐标 }}}_{\text {x用单位向量正交基V表示}}}_{\text {对单位正交基V进行旋转，使之变为标准正交基I}}} _{\text {对单位正交基V进行拉伸}}}_{\text {对拉伸后正交基进行旋转}} \tag{9}\\ \end{align*}

​ 如(9)所示, 矩阵 A对向量 \vec{x} 进行线性变换, 其先将向量 \vec{x} 用单位正交基V进行表示. 然后使用正交矩阵 V^T 进行旋转, 由正交矩阵的性质我们可知 VV^T=V^TV=I , 所以旋转之后我们可得到标准正交基 I. 然后使用矩阵 \sum 对标准正交基 I 进行拉伸, 使得 x轴和y轴 分别拉伸 \sigma_1,\sigma_2 倍的长度. 最后再使用正交矩阵U对拉伸之后的正交基进行旋转, 得到最终的基, 从而得到最终的向量为:

\begin{align*} A\vec{x}&=[\sigma_1\mu_1,\sigma_2\mu_2]\cdot \left[\begin{matrix} \xi_1 \\ \xi_2\end{matrix}\right]\\ &=\xi_1\sigma_1\mu_1 + \xi_2\sigma_2\mu_2 \tag{10} \end{align*}

在几何上看，SVD分解就可以看作是讲一个矩阵进行旋转，然后缩放，然后再旋转的的操作：

通过SVD, 我们找到了能代表矩阵A作为线性变换时最本质的操作.而 \sigma_1,\sigma_2 就是所谓的奇异值, 表示对标准正交基各个轴进行拉伸的程度.

四、SVD的求解过程

​ 上述关于SVD在二维平面上的结论可以轻易地推广到多维情况. 那SVD具体如何求解呢? 由(6)我们知道SVD能使矩阵A进行分解, 现在由(6)出发我们来构造矩阵 U,\sum,V , 具体地, 我们有:

\begin{align*} AA^T&=U\sum{}{}V\sum{}^TU^T\\ &= U\sum{}^2U^T\tag{11}\\ A^TA&=V\sum{}{}^TU^TU\sum{}V^T\\ &= V\sum{}^2V^T\tag{12} \end{align*}

由实对称矩阵必可正交对角化, 即

\begin{align*} \mathbf{A}=\mathbf{Q} \boldsymbol{\Lambda} \mathbf{Q}^{\top} \tag{13} \end{align*}

其中矩阵 \mathbf{Q}为正交矩阵, 即满足 \mathbf{Q}^T=\mathbf{Q}^{-1} . 矩阵 \boldsymbol{\Lambda} = diga(\lambda_1,\cdots,\lambda_n) 为矩阵A的特征值所组成的对角矩阵. 而矩阵 AA^T,A^TA 是实对称矩阵, 矩阵 U，V是正交矩阵, 矩阵 \sum{}^2 是对角矩阵, 所以由(11), (12), (13), 我们对矩阵 AA^T,A^TA 进行正交对角化, 即可得到矩阵 U，V. 再由

\begin{align*} \because \mathbf{A}&=\mathbf{U} \mathbf{\Sigma V}^{\top} \\ \mathbf{A V}&=\mathbf{U} \mathbf{\Sigma} \\ \mathbf{A} v_{i}&=\sigma_{i} \mu_{i} \\ \therefore \sigma_{i}&=\frac{\mathbf{A} v_{i}}{\mu_{i}} \tag{14} \end{align*}

由(14)我们便可得到矩阵 \sum ,由(11), (12), (13), (14)即可得完整的SVD分解.