机器学习日记(四):奇异值分解

引言

在学习奇异值分解前，请务必看一下以下对于奇异值的直观理解：奇异值的物理意义是什么？

奇异值分解是一种矩阵因子分解方法，任意一个 \(m×n\) 矩阵，都可以表示为三个矩阵的乘积(因子分解)形式，分别是 \(m\) 阶正交矩阵、由降序排列的非负的对角线元素组成的 \(m×n\) 矩阵对角矩阵和 \(n\) 阶正交矩阵，称为该矩阵的奇异值分解。矩阵的奇异值分解一定存在，但不唯一。奇异值分解可以看作是矩阵数据压缩的一种方法，即用因子分解的方式近似地表示原始矩阵，这种近似是在平方损失意义下的最有近似。

一、定理与定义

定义1  (奇异值分解) 矩阵的奇异值分解是指，将一个非零的 \(m×n\) 实矩阵 \(A\), \(A\in R^{m×n}\)，表示为以下三个实矩阵乘积形式的运算，即进行矩阵因子分解：

\[A=U\sum V^T\]

其中 \(U\) 是 \(m\) 阶正交矩阵，\(V\) 是 \(n\) 阶正交矩阵，\(\sum\) 是由降序排列的非负的对角线元素组成的 \(m×n\) 矩阵对角矩阵，

\[UU^T=I\]

\[VV^T=I\]

\[\sum = diag(\sigma_1,\sigma_2,\cdots,\sigma_p)\]

\[\sigma_1\geq \sigma_2 \geq \cdots \geq \sigma_p \geq 0\]

\[p=min(m,n)\]

\(U\sum V^T\) 称为矩阵 \(A\) 的奇异值分解， \(\sigma_i\) 称为矩阵 \(A\) 的奇异值， \(U\) 的列向量称为左奇异向量，\(V\) 的列向量称为右奇异向量。

那么任意给定一个实矩阵，其奇异值分解是否一定存在呢？答案是肯定的，下面的奇异值分解的基本定理给予保证。

---

定理1  (奇异值分解基本定理) 若 \(A\) 为一 \(m×n\) 实矩阵，\(A\in R^{m×n}\)，则 \(A\) 的奇异值分解存在

\[A=U\sum V^T\]

证明：证明是构造性的，对给定的矩阵 \(A\)，构造出其奇异值分解的各个矩阵。为了方便，不放假设 \(m\geq n\)，如果 \(m<n\) 证明仍然成立。证明由三步完成。

1. 确定 \(V\) 和 \(\sum\)

首先构造 \(n\) 阶正交实矩阵 \(V\) 和 \(m×n\) 矩阵对角实矩阵 \(\sum\)。

矩阵 \(A\) 是 \(m×n\) 实矩阵，则矩阵 \(A^TA\) 是 \(n\) 阶实对称矩阵。因而 \(A^TA\) 的特征值都是实数，并且存在一个 \(n\) 阶正交实矩阵 \(V\) 实现 \(A^TA\) 的对角化，使得 \(V^T(A^TA)V= \Lambda\) 成立，其中 \(\Lambda\) 是 \(n\) 阶对角矩阵，其对角线元素由 \(A^TA\) 的特征值组成。

而且，\(A^TA\) 的特征值都是非负的。事实上，令 \(\lambda\) 是 \(A^TA\) 的一个特征值，\(x\) 是对应的特征向量，则

\[||Ax||^2=x^TA^TAx=\lambda x^Tx=\lambda ||x||^2\]

于是

\[\lambda=\frac{||Ax||^2}{||x||^2}\geq0\]

可以假设正交矩阵 \(V\) 的列的排列使得对应的特征值形成降序排列

\[</p>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n \geq 0\]

计算特征值的平方根（实际就是矩阵 \(A\) 的奇异值）

\[\sigma_j=\sqrt{\lambda_j}，j=1,2,\cdots,n\]

设矩阵 \(A\) 的秩是 \(r\) , \(rank(A) = r\)，则矩阵 \(A^TA\) 的秩也是 \(r\)。由于 \(A^TA\) 是对称矩阵，它的秩等于正的特征值的个数，所以

\[\lambda_1 \geq \lambda_2 \geq \cdots \lambda_r >0，\lambda_{r+1}=\lambda_{r+2}=\cdots=\lambda_n=0\]

对应的有

\[\sigma_1 \geq \sigma_2 \geq \cdots \sigma_r >0，\sigma_{r+1}=\sigma_{r+2}=\cdots=\sigma_n=0\]

令

\[V_1 = [v_1\quad v_2\quad \cdots\quad v_r]，V_2=[v_{r+1}\quad v_{r+2}\quad \cdots\quad v_n]\]

其中 \(v_1,\cdots,v_r\) 为 \(A^TA\) 的正特征值对应的特征向量，\(v_{r+1},\cdots,v_n\) 为 \(0\) 特征值对应的特征向量，则

\[V = [V_1\quad V_2]\]

这就是矩阵 \(A\) 的奇异值分解中的 \(n\) 阶正交矩阵 \(V\)。

令

\[\sum_1=\left[\begin{matrix}\sigma_1 &\quad & \quad &\quad \\ \quad & \sigma_2 &\quad & \quad \\ \quad& \quad & \cdots & \quad \\ \quad & \quad & \quad & \sigma_r \end{matrix}\right]\]

则 \(\sum_1\) 是一个 \(r\) 阶对角矩阵，其对角线元素为按降序排列的正的 \(\sigma_1,\cdots,\sigma_r\)，于是 \(m×n\) 矩阵对角矩阵 \(\sum\) 可以表示为

\[\sum = \left[\begin{matrix} \sum_1 & 0 \\ 0 & 0\end{matrix}\right]\]

这就是矩阵 \(A\) 的奇异值分解中的 \(m×n\) 矩阵对角矩阵 \(\sum\)。

下面推出后面要用到的一个公式。 \(V_2\) 的列向量是 \(A^TA\) 对应于特征值为 \(0\) 的特征向量。因此

\[A^TAv_j=0，j=r+1,\cdots,n\]

于是， \(V_2\) 的列向量构成了 \(A^TA\) 的零空间 \(N(A^TA)\)，而 \(N(A^TA)=N(A)\)。所以 \(V_2\) 的列向量构成 \(A\) 的零空间的一组标准正交基。因此

\[AV_2=0\]

由于 \(V\) 是正交矩阵，所以

\[I=VV^T=V_1V_1^T+V_2V_2^T\]

\[A =AI=AV_1V_1^T+AV_2V_2^T=AV_1V_1^T\]

2. 确定 \(U\)

接着构造 \(m\) 阶正交实矩阵 \(U\)。

令

\[u_j=\frac{1}{\sigma_j}Av_j，j=1,2,\cdots,r\]

\[U_1=[u_1\quad u_2 \quad \cdots \quad u_r]\]

则有

\[AV_1=U_1 \sum_{1}\]

\(U_1\) 的列向量构成了一组标准正交基。

若 \(R(A)^\bot\) 表示 \(R(A)\) 的正交补，则有 \(R(A)\) 的维数为 \(r\)， \(R(A)^\bot\) 的维数为 \(m-r\)，两者的维数之和等于 \(m\)。而且有 \(R(A)^\bot =N(A^T)\) 成立。

令 \(\{u_{r+1},u_{r+2},\cdots,u_m\}\) 为 \(N(A^T)\) 的一组标准正交基，并令

\[U_2 = [u_{r+1}\quad u_{r+2} \quad \cdots \quad u_m]\]

\[U = [U_1\quad U_2]\]

则 \(u_1,u_2,\cdots,u_m\) 构成了 \(R^m\) 的一组标准正交基。因此，\(U\) 是 \(m\) 阶正交矩阵，这就是矩阵 \(A\) 的奇异值分解中的 \(m\) 阶正交矩阵。

3. 证明 \(U\sum V^T=A\)

\[U\sum V^T= [U_1\quad U_2]\left[\begin{matrix} \sum_1 & 0 \\ 0 & 0\end{matrix}\right]\left[\begin{matrix}V_1^T \\ V_2^T \end{matrix}\right]\]

\[=U_1 \sum_{1} V_1^T\]

\[=AV_1V_1^T\]

\[=A\]

至此证明了矩阵 \(A\) 存在奇异值分解。

二、紧奇异值分解与截断奇异值分解

定理1给出的奇异值分解

\[A=U\sum V^T\]

又称为矩阵的完全奇异值分解。实际常用的是奇异值分解的紧凑形式和截断形式。紧奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵低秩的奇异值分解。

2.1紧奇异值分解

设有 \(m×n\) 实矩阵 \(A\)，其秩为 \(rank(A)=r，r\leq min(m,n)\)，则称 \(U_r\sum_rV_r^T\) 为 \(A\) 的紧奇异值分解，即

\[A=U_r \sum_{r} V_r^T\]

其中 \(U_r\) 是 \(m×r\) 矩阵，\(V_r\) 是 \(n×r\) 矩阵，\(\sum_r\) 是 \(r\) 阶对角矩阵；矩阵 \(U_r\) 由完全奇异值分解中 \(U\) 的前 \(r\) 列、矩阵 \(V_r\) 由 \(V\) 的前 \(r\) 列、矩阵 \(\sum_r\) 由 \(\sum\) 的前 \(r\) 个对角线元素得到。紧奇异值分解的对角矩阵 \(\sum_r\) 的秩与原始矩阵 \(A\) 的秩相等。

2.2 截断奇异值分解

在矩阵的奇异值分解中，只取最大的 \(k\) 个奇异值 \((k<r)\) 对应的部分，就得到矩阵的截断奇异值分解。实际应用中提到的矩阵的奇异值分解时，通常指截断奇异值分解。

设 \(A\) 为 \(m×n\) 实矩阵，其秩 \(rank(A)=r\)，且 \(0<k<r\)，则称 \(U_k\sum_kV_k^T\) 为矩阵 \(A\) 的截断奇异值分解

\[A \approx U_k \sum_{k} V_k^T\]

其中 \(U_k\) 是 \(m×\)k 矩阵，\(V_k\) 是 \(n×k\) 矩阵，\(\sum_k\) 是 \(k\) 阶对角矩阵；矩阵 \(U_k\) 由完全奇异值分解中 \(U\) 的前 \(k\) 列、矩阵 \(V_k\) 由 \(V\) 的前 \(k\) 列、矩阵 \(\sum_k\) 由 \(\sum\) 的前 \(k\) 个对角线元素得到。对角矩阵 \(\sum_k\) 的秩比原始矩阵 \(A\) 的秩低。

在实际应用中，常常需要对矩阵的数据进行压缩，将其近似表示，奇异值分解提供了一种方法。紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩。

三、几何解释

从线性变换的角度理解奇异值分解，\(m×n\) 矩阵 \(A\) 表示从 \(n\) 维空间 \(R^n\) 到 \(m\) 维空间 \(R^m\) 的一个线性变换，

\[T:x\rightarrow Ax\]

\(x\in R^n，Ax\in R^m\)，\(x\) 和 \(Ax\) 分别是各自空间的向量。线性变换可以分解为三个简单的变换：一个坐标系的旋转或发射变换、一个坐标轴的缩放变换、另一个坐标系的旋转或反射变换。奇异值定理保证这种分解一定存在。这就是奇异值分解的几何解释。

对矩阵 \(A\) 进行奇异值分解，得到 \(A=U\sum V^T\) ，\(V\) 和 \(U\) 都是正交矩阵。所以 \(V\) 的列向量 \(v_1,v_2,\cdots,v_n\) 构成 \(R^n\) 空间的一组标准正交基，表示 \(R^n\) 中的正交坐标系的旋转或反射变换； \(U\) 的列向量 \(u_1,u_2,\cdots,u_m\) 构成 \(R^m\) 空间的一组标准正交基，表示 \(R^m\) 中的正交坐标系的旋转或反射变换； \(\sum\) 的对角元素 \(\sigma_1,\sigma_2,\cdots,\sigma_n\) 是一组非负实数，表示 \(R^n\) 中的原始正交坐标系坐标轴的 \(\sigma_1,\sigma_2,\cdots,\sigma_n\) 倍的缩放变换。

任意一个向量 \(x\in R^n\)，经过基于 \(A=U\sum V^T\) 的线性变换，等价于经过坐标系的旋转或反射变换 \(V^ T\)，坐标轴的缩放变换 \(\sum\)，以及坐标系的旋转或反射变换 \(U\)，得到向量 \(Ax\in R^m\)。下图给出了直观的几何解释。

四、主要性质

1. 设矩阵 \(A\) 的奇异值分解为 \(A=U\sum V^T\)，则以下关系成立：

\[A^TA=(U \sum V^T)^T(U \sum V^T)=V(\sum^{T} \sum)V^T\]

\[AA^T = (U\sum V^T)(U \sum V^T)^T=U(\sum \sum^{T})U^T\]

也就是说，矩阵 \(A^TA\) 和 \(AA^T\) 的特征分解存在，且可以有矩阵 \(A\) 的奇异值分解的矩阵表示。\(V\) 的列向量是 \(A^TA\) 的特征向量，\(U\) 的列向量是 \(AA^T\) 的特征向量， \(\sum\) 的奇异值是\(A^TA\) 和 \(AA^T\) 的特征值的平方根。

2. 在矩阵 \(A\) 的奇异值分解中，奇异值、左奇异向量和右奇异向量之间存在对于关系。

由 \(A=U\sum V^T\) 易知

\[AV=U\sum\]

比较这一等式两端的第 \(j\) 列，得到

\[Av_j=\sigma_ju_j \tag{关系一}\]

这是矩阵 \(A\) 的右奇异向量和奇异值、左奇异向量的关系。

类似的，由

\[A^TU = V \sum^{T}\]

得到

\[A^Tu_j=\sigma_jv_j，j=1,2,\cdots,r \tag{关系二}\]

\[A^Tu_j=0，j=r+1,r+2,\cdots,m \tag{关系三}\]

这是矩阵 \(A\) 的左奇异向量和奇异值、右奇异向量的关系。

3. 矩阵 \(A\) 的奇异值分解中，奇异值 \(\sigma_1,\cdots,\sigma_n\) 是唯一的，而矩阵 \(U\) 和 \(V\) 不是唯一的。

4. 矩阵 \(A\) 和 \(\sum\) 的秩相等，等于正奇异值的个数 \(r\)。

五、奇异值分解的计算

给定 \(m×n\) 矩阵 \(A\)，可以按照上面的叙述写出矩阵奇异值分解的计算过程。

1. 首先求 \(A^TA\) 的特征值和特征向量。

计算对称矩阵 \(W=A^TA\)。

求解特征方程

\[(W-\lambda I)x=0\]

得到特征值 \(\lambda_i(i=1,2,\cdots,n)\)，并将特征值由大到小排列

\[\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0\]

将特征值带入特征方程求得对应的特征向量。

2. 求 \(n\) 阶正交矩阵 \(V\)

将特征向量单位化， 得到单位特征向量 \(v_1,\cdots,v_n\)，构成 \(n\) 阶正交矩阵 \(V\) :

\[V=[v_1\quad v_2\quad \cdots\quad v_n]\]

3. 求 \(m×n\) 对角矩阵 \(\sum\)

计算 \(A\) 的奇异值

\[\sigma_i=\sqrt{\lambda_i}，i=1,2,\cdots,n\]

构造 \(m×n\) 矩阵对角矩阵 \(\sum\)，主对角线元素是奇异值，其余元素是 \(0\)，

\[\sum = diag(\sigma_1,\sigma_2,\cdots,\sigma_n)\]

4. 求 \(m\) 阶正交矩阵 \(U\)

对 \(A\) 的前 \(r\) 个正奇异值，令

\[u_j=\frac{1}{\sigma_j}Av_j，j=1,2,\cdots,r\]

得到

\[U_1=[u_1\quad u_2\quad \cdots \quad u_r]\]

利用上面所述性质等式求 \(A^T\) 的零空间的一组标准正交基 \(\{u_{r+1}，u_{r+2},\cdots,u_m\}\)，令

\[U_2=[u_{r+1}\quad u_{r+2}\quad \cdots \quad u_m]\]

并令

\[U=[U_1\quad U_2]\]

5. 得到奇异值分解

\[A=U\sum V^T\]

六、奇异值分解与矩阵近似

6.1 弗罗贝尼乌斯范数

奇异值分解也是一种矩阵近似的方法，这个近似是在弗罗贝尼乌斯范数意义下的近似。矩阵的弗罗贝尼乌斯范数是向量的 \(L_2\) 范数的直接推广，对应着机器学习中平方损失函数。

定义 （弗罗贝尼乌斯范数） 设矩阵 \(A \in R^{m×n}，A=[a_{ij}]_{m×n}\)，定义矩阵 \(A\) 的弗罗贝尼乌斯为

\[||A||_F = \left(\mathop{\sum}\limits_{i=1}^{m}\mathop{\sum}\limits_{j=1}^{n}(a_{ij})^2\right)^{1\over2}\]

引理     设矩阵 \(A \in R^{m×n}\)，\(A\) 的奇异值分解为 \(U\sum V^T\)，其中 \(\sum=diag(\sigma_1,\sigma_2,\cdots,\sigma_n)\)，则

\[||A||_F = (\sigma_1^2+\sigma_2^2+\cdots+\sigma_n^2)^{1\over 2}\]

6.2 矩阵的最优近似

奇异值分解是在平方损失(弗罗贝尼乌斯范数)意义下对矩阵的最优近似，即数据压缩。

定理1       设矩阵 \(A\in R^{m×n}\)，矩阵得秩 \(rank(A)=r\)，并设 \(M\) 为 \(R^{m×n}\) 中所有秩不超过 \(k\) 的矩阵集合， \(0<k<r\)，则存在一个秩为 \(k\) 的矩阵 \(X \in M\)，使得

\[||A-X||_F=\mathop{min}\limits_{S\in M} ||A-S||_F\]

称矩阵 \(X\) 为矩阵 \(A\) 在弗罗贝尼乌斯范数意义下的最优近似。

定理2     设矩阵 \(A\in R^{m×n}\)，矩阵得秩 \(rank(A)=r\)，有奇异值分解\(A=U\sum V^T\)，并设 \(M\) 为 \(R^{m×n}\) 中所有秩不超过 \(k\) 的矩阵的集合，\(0<k<r\)，若秩为 \(k\) 的矩阵 \(X \in M\) 满足

\[||A-X||_F=\mathop{min}\limits_{S\in M} ||A-S||_F\]

则

\[||A-X||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_{n}^2)^{1\over2}\]

特别的，若 \(A^{'}=U\sum^{'}V^T\)，其中

\[\sum^{'}=\left[\begin{matrix} \sigma_1 & \quad& \quad& \quad& \quad& \quad \\ \quad & \ddots & \quad& \quad & 0 & \quad \\ \quad & \quad & \sigma_k & \quad& \quad& \quad \\ \quad& \quad& \quad &0 & \quad& \quad\\ \quad & 0 & \quad& \quad & \ddots & \quad \\ \quad & \quad& \quad& \quad& \quad&0\end{matrix}\right]=\left[\begin{matrix} \sum_k & 0 \\ 0 & 0\end{matrix}\right]\]

则

\[||A-A^{'}||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_{n}^2)^{1\over2}=\mathop{min}\limits_{S\in M} ||A-S||_F\]

上式表明，在秩不超过 \(k\) 的矩阵集合中，存在矩阵 \(A\) 的弗罗贝尼乌斯范数意义下的最优近似矩阵 \(X\)。 \(A^{'}=U\sum^{'}V^T\) 是达到最优值的一个矩阵。

6.3 矩阵的外积展开式

矩阵 \(A\) 的奇异值分解也可以由外积形式表示。事实上，若将 \(A\) 的奇异值分解看成矩阵 \(U\sum\) 和 \(V^T\) 的乘积，将 \(U\sum\) 按列向量分块，将 \(V^T\)按行向量分块，即得

\[U\sum=[\sigma_1u_1\quad \sigma_2u_2\quad\cdots\quad \sigma_nu_n]\]

\[V^T=\left[\begin{matrix} v_1^T \\ v_2^T \\ \vdots \\ v_n^T\end{matrix}\right]\]

则

\[A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_nu_nv_n^T\]

上式称为矩阵 \(A\) 的外积展开式。其中 \(u_kv_k^T\) 为 \(m×n\) 的矩阵，是列向量 \(u_k\) 和行向量 \(v_k^T\) 的外积，其第 \(i\) 行第 \(j\) 列元素为 \(u_k\) 的第 \(i\) 个元素与 \(v_k^T\) 的第 \(j\) 个元素的乘积。

一般的，设矩阵

\[A_k=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T\]

则 \(A_k\) 的秩为 \(k\)，并且 \(A_k\) 是秩为 \(k\) 的矩阵在弗罗贝尼乌斯范数意义下 \(A\) 的最优近似矩阵。矩阵 \(A_k\) 就是 \(A\) 的截断奇异值分解。

由于通常奇异值 \(\sigma_i\) 递减很快，所以 \(k\) 取很小值时， \(A_k\) 也可以对 \(A\) 有很好得近似。

七、Reference

• 李航《统计学习方法》