[线性代数] - 奇异值分解

我们到目前为止讨论了许多分解，那么有没有那么一种万能的分解呢？这就是奇异值分解。

任一$m \times n$的矩阵$A$都可以分解为一个$m \times m$的正交矩阵，一个$m \times n$的对角矩阵$\Sigma$，和一个$n \times n$的正交矩阵$V$的转置$V^T$，即：

$A = U\Sigma V^T$

奇异值

设$A$是$m \times n$的矩阵，这里$A$不是方阵，但是我们知道$\mathbf{A^TA}$是方阵，我们可以对$\mathbf{A^TA}$进行操作。

设$\mathbf{A^TA}$的特征值为

$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$

其对应的标准正交特征向量为

$\lbrace V_1, V_2, \cdots, V_n \rbrace$

则有

$A^TAV_i = \lambda_iV_i$

两边左乘$\mathbf{v_i^T}$

$V_i^TA^TAV_i = V_i^T\lambda_iV_i$

整理可得

$(AV_i)^T(AV_i) = \lambda V_i^TV_i$

因为$\mathbf{v_i}\mathbf{v_i} = 1$，即可得

$\parallel AV_i\parallel ^2 = \lambda_i$

可以得到

$\parallel AV_i\parallel = \sqrt{\lambda_i}$

其中，$\sqrt{\lambda_i}$称为$A$的奇异值

假设 $A^TA$的特征值为$\lambda$，那么$\sqrt{\lambda}$称为$A$的奇异值，记为$\sigma$

$A$的奇异值就是向量$AV_i$的长度。当奇异值为$0$的时候，$AV = 0$

我们再来看看$A\mathbf{v_i}$

$(AV_j)^T(AV_i) = \lambda V_j^TV_i = 0$

于是我们可以得出：

$\lbrace A\mathbf{v_1}, A\mathbf{v_2}, \cdots, A\mathbf{v_n}\rbrace$是一组正交向量集

一般情况

设$A$是$m \times n$的矩阵，且有$r(r \leq n)$个不等于$0$的奇异值，则

$\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > \sigma_{r+1} = \sigma_{r+2} = \cdots = \sigma_{r+n} = 0$

即

$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_r > \lambda_{r+1} = \lambda_{r+2} = \cdots = \lambda_{r+n} = 0$

可以知道

$\begin{cases} A\mathbf{v_1} \neq 0 & (1 \leq i \leq r) \\ A\mathbf{v_1} = 0 & (r < i \leq n) \end{cases}$

于是我们可以得到

$\lbrace AV_1, AV_2, \cdots, AV_r\rbrace$是一组线性无关的正交向量集

这里$AV_i \in C(A)$，其中$C(A)$列空间，
因为$\lbrace \mathbf{v_1}, \mathbf{v_2}, \cdots, \mathbf{v_n} \rbrace$是$A^TA$的标准正交向量，因此$\lbrace \mathbf{v_1}, \mathbf{v_2}, \cdots, \mathbf{v_n} \rbrace$是$\mathbb{R}^n$的一个基，于是对于$x \in \mathbb{R}^n$

$\mathbf{x} = c_1\mathbf{v_1} + c_2\mathbf{v_2} + \cdots + c_n\mathbf{v_n}$

于是对于列空间$C(A)$，有

$\begin{aligned} y &= A\mathbf{x} \\ &= A(c_1\mathbf{v_1} + c_2\mathbf{v_2} + \cdots + c_n\mathbf{v_n}) \\ &= c_1A\mathbf{v_1} + c_2A\mathbf{v_2} + \cdots + c_nA\mathbf{v_n} \\ &= c_1AV_1 + c_2AV_2 + \cdots + c_rAV_r + c_{r+1}AV_{r+1} + \cdots + c_{n}AV_{n} \\ &= c_1AV_1 + c_2AV_2 + \cdots + c_rAV_r + 0 + \cdots + 0 \\ &= c_1AV_1 + c_2AV_2 + \cdots + c_rAV_r \end{aligned}$

因此$\lbrace AV_1, AV_2, \cdots, AV_r\rbrace$是$C(A)$的一个正交基，由于这组基的向量个数是$r$，因此$C(A)$的维数$dimC(A)$也为$r$，即

$rankA = dimC(A) = r$

将$\lbrace AV_1, AV_2, \cdots, AV_r\rbrace$标准化

$\mathbf{u}_i = \frac{AV_i}{\parallel AV_i\parallel } = \frac{1}{\sigma_i}AV_i \quad (i \leq i \leq r)$

即

$AV_i = \sigma_i\mathbf{u}_i$

于是$\lbrace \mathbf{u}_1, \mathbf{u}_2, \cdots, \mathbf{u}_n \rbrace$就是$C(A)$下的一组标准正交基，再从$A$的左零空间取$m - r$个标准正交向量$\lbrace \mathbf{u}_{r+1}, \mathbf{u}_{r+2}, \cdots, \mathbf{u}_m$，并将他们合并，得到$\mathbb{R}^m$下的一个标准正交基。令

$\begin{aligned} U &= \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_m \end{bmatrix} \\ V &= \begin{bmatrix} V_1 & V_2 & \cdots & V_n \end{bmatrix} \end{aligned}$

可以知道$U, V$都是正交矩阵，计算$AV$

$\begin{aligned} AV &= A\begin{bmatrix} V_1 & V_2 & \cdots & V_m \end{bmatrix} \\ &= \begin{bmatrix} AV_1 & AV_2 & \cdots & AV_m \end{bmatrix} \\ &= \begin{bmatrix} AV_1 & AV_2 & \cdots & AV_r & 0 & \cdots & 0 \end{bmatrix} \\ &= \begin{bmatrix} \sigma_1\mathbf{u}_1 & \sigma_2\mathbf{u}_2 & \cdots & \sigma_r\mathbf{u}_r & 0 & \cdots & 0 \end{bmatrix} \\ \\ &= U\begin{bmatrix} \sigma_1 & 0 & \cdots & 0 & | & 0_{11} & \cdots & 0_{1(n-r)} \\ 0 & \sigma_2 & \cdots & 0 & | & 0_{21} & \cdots & 0_{2(n-r)} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_r & | & 0_{r1} & \cdots & 0_{r(n-r)} \\ - & - & - & - & & - & - & - \\ 0_{11} & 0_{12} & \cdots & 0_{1r} & | & 0_{11} & \cdots & 0_{(n-r)r} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots & \ddots & \vdots \\ 0_{(m-r)1} & 0_{(m-r)2} & \cdots & 0_{(m-r)r} & | & 0_{(m-r)1} & \cdots & 0_{(m-r)(n-r)} \end{bmatrix} \end{aligned}$

令

$D_{r \times r} = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \sigma_2 & \cdots & \sigma_r \\ \end{bmatrix}$

则

$AV = \begin{bmatrix}U_{m\times r} & U_{m\times (m-r)}\end{bmatrix}\begin{bmatrix} D_{r \times r} & \mathbf{O}_{r \times (n-r)} \\ \mathbf{O}_{(m-r) \times r} & \mathbf{O}_{(m-r) \times (n-r)} \end{bmatrix}$

令

$\Sigma = \begin{bmatrix} D_{r \times r} & \mathbf{O}_{r \times (n-r)} \\ \mathbf{O}_{(m-r) \times r} & \mathbf{O}_{(m-r) \times (n-r)} \end{bmatrix}$

则

$AV = U\Sigma$

由于$V$是正交矩阵，因此$V$是可逆的，且$V^{-1} = V^T$，即

$A = U\Sigma V^{-1} = U\Sigma V^T$

上式即为$A$的奇异值分解，其中$U$的列向量称为$A$的左奇异向量，$V$的列向量称为$A$的右奇异向量

我们知道$V$是$A^TA$的特征向量矩阵，那么现在来看看$U$是什么

$\begin{aligned} \mathbf{u}_i = \frac{AV_i}{\parallel AV_i\parallel } &= \frac{1}{\sigma_i}AV_i \\ AA^T\mathbf{u}_i &= AA^T\frac{1}{\sigma_i}AV_i \\ &= \frac{1}{\sigma_i}A(A^TAV_i) \\ &= \frac{1}{\sigma_i}A(\lambda_iV_i) \\ &= \frac{\lambda_i}{\sigma_i}AV_i \quad (i \leq i \leq r) \end{aligned}$

于是在$i \leq i \leq r$的时候

$AA^T\mathbf{u}_i = \frac{\lambda_i}{\sigma_i}AV_i$

现在考虑$r < i \leq m$的时候，此时

$\mathbf{u}_i \in N(A^T)$

因此

$\mathbf{u}_i^TA = 0$

取转置

$A^T\mathbf{u}_i = 0$

两边左乘$A$

$\begin{aligned} AA^T\mathbf{u}_i &= A0 \\ &= 0\mathbf{u}_i \end{aligned}$

设$\lambda_i' = 0 (r < i \leq m)$，则

$AA^T\mathbf{u}_i = \lambda_i'\mathbf{u}_i$

就可以知道

$\begin{cases} AA^T\mathbf{u}_i &= \lambda_i\mathbf{u}_i (i \leq i \leq r) \\ AA^T\mathbf{u}_i &= \lambda_i'\mathbf{u}_i (r < i \leq m) \end{cases}$

---

$V$是$A^TA$的特征向量矩阵
$U$是$AA^T$的特征向量矩阵

$A^TA$的特征值矩阵

$\begin{bmatrix} \lambda_1 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & \lambda_r & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & 0_{r+1} & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & 0 \\ 0 & 0 & 0 & 0 & 0 & \cdots & 0_\color{red}{n} \end{bmatrix}$

$AA^T$的特征值矩阵

$\begin{bmatrix} \lambda_1 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & \lambda_r & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & 0_{r+1} & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & 0 \\ 0 & 0 & 0 & 0 & 0 & \cdots & 0_\color{red}{m} \end{bmatrix}$

奇异值分解步骤

• 计算对角矩阵$A^TA$的特征值与特征向量
• 将特征值排列为$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$取不为$0$的特征值（假设前$r$个特征值不为$0$）构造由$A$的奇异值组成的对角阵

$D_{r \times r} = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_r \end{bmatrix}$

进而构造$\Sigma$

$\Sigma = \begin{bmatrix} D_{r \times r} & \mathbf{O}_{r \times (n-r)} \\ \mathbf{O}_{(m-r) \times r} & \mathbf{O}_{(m-r) \times (n-r)} \end{bmatrix}$

• 然后构造$V$，假设对应于$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$的标准正交特征向量为$V_1, V_2, \cdots, V_n$则：

$V = \begin{bmatrix} V_1 & V_2 & \cdots & V_n \end{bmatrix}$

• 通过

$\mathbf{u}_i = \frac{1}{\sigma_i}AV_i$

计算出前$r$个$\mathbf{u}_1$，再找出$N(A^T)$的$m-r$个基向量，进行正交化和标准化

$U = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_n \end{bmatrix}$

• 即可得出$A = U\Sigma V^T$

奇异值分解与矩阵近似的应用

在文件压缩，特征抽取和一些噪音消除的分析应用中，我们希望有一个矩阵的最佳近视矩阵，通过改变矩阵的秩来控制近似误差，这样的问题称为矩阵近似

问题：若$A$是一个$m \times n$的实矩阵，求同阶矩阵$\hat{A}$使得$\parallel A - \hat{A}\parallel$最小，并且满足$rank\hat{A} < rankA$。

正交变换对范数的影响

为了求解此问题，我们需要先知道正交变换对Frobenius不会产生影响

$\begin{aligned} \parallel QA\parallel^2_F &= tr((QA)^T( QA)) = tr(A^T\color{red}Q^TQ\color{bloack}A) = tr(A^TA) = \parallel A\parallel^2_F \\ \parallel AQ\parallel^2_F &= tr((AQ)(AQ)^T) = tr(A\color{red} QQ^T\color{bloack}A^T) = tr(AA^T) = \parallel A\parallel^2_F \end{aligned}$

其中$Q$是任意的正交矩阵，再看奇异值分解

求解过程

$A = U\Sigma V^T$，其中$U,V^T$均为正交矩阵，于是可以得出

$\parallel A\parallel _F = \parallel \Sigma\parallel _F = \sqrt{\sum_{i=1}^r\sigma^2_i}$

将目标函数改写

$\begin{aligned} min\parallel A - \hat{A}\parallel _F &= min\parallel U\Sigma V^T - \hat{A}\parallel_F \\ &= min\parallel U^T(U\Sigma V^T - \hat{A})V\parallel_F \\ &= min\parallel \Sigma - U^T\hat{A}V\parallel_F \end{aligned}$

我们注意到

$\Sigma = \begin{bmatrix} D_{r \times r} & \mathbf{O}_{r \times (n-r)} \\ \mathbf{O}_{(m-r) \times r} & \mathbf{O}_{(m-r) \times (n-r)} \end{bmatrix}$

是一个对角矩阵，那么为了让结果最小，$U^T\hat{A}V$也需要是一个对角线矩阵，这样才能使平方和最小，即

$U^T\hat{A}V = \begin{bmatrix} D_{k \times k}' & \mathbf{O}_{k \times (n-k)} \\ \mathbf{O}_{(m-k) \times k} & \mathbf{O}_{(m-k) \times (n-k)} \end{bmatrix}$

因此

$\hat{A} = U\begin{bmatrix} D' & \mathbf{O} \\ \mathbf{O} & \mathbf{O} \end{bmatrix} V^T$

则原问题可以继续化简

$min\parallel D - D'\parallel _F = min\sqrt{\sum_{i=1}^r(\sigma_i - d_i')^2}$

当$rank\hat{A} = k$时，$D'$有$k$个不为$0$的主对角元，我们知道$D$里的对角主元$\sigma_i$是降序排列的，所以当近似矩阵$\hat{A}$保留最大$k$个奇异值时，目标函数取得最小。此时最小值等于

$min\parallel D - D'\parallel _F = min\sqrt{\sum_{i=k+1}^r\sigma_i'^2}$

参考资料

SVD 於矩陣近似的應用