[人工智能] 【李航】统计学习方法--15. 奇异值分解（详细推导）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 【李航】统计学习方法--15. 奇异值分解（详细推导） -> 正文阅读

[人工智能]【李航】统计学习方法--15. 奇异值分解（详细推导）

在这里插入图片描述

文章目录

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

15.1 奇异值分解的定义与性质

15.1.1 定义与定理

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

$\Sigma V^{\mathrm{T}}$

其中 $U$ 是 $m$ 阶正交矩阵 ( orthogonal matrix ), $V$ 是 $n$ 阶正交矩阵, $\Sigma$ 是由降序排列的非负的对角线元素组成的 $\times n$ 矩形对角矩阵 ( rectangular diagonal matrix ), 满足

$\begin{array}{l} U U^{\mathrm{T}}=I \\ V V^{\mathrm{T}}=I \\ \Sigma=\operatorname{diag}\left(\sigma_{1}, \sigma_{2}, \cdots, \sigma_{p}\right) \\ \sigma_{1} \geqslant \sigma_{2} \geqslant \cdots \geqslant \sigma_{p} \geqslant 0 \\ p=\min (m, n) \end{array}$

$\Sigma V^{\mathrm{T}}$ 称为矩阵 $A$ 的奇异值分解( singular value decomposition, $\left.\mathrm{SVD}\right), \sigma_{i}$ 称为矩阵 $A$ 的奇异值 ( singular value ), $U$ 的列向量称为左奇异向量 ( left singular vector ), $V$
的列向量称为右奇异向量 ( right singular vector)。

正交矩阵：满足 $A^{T} A=I$ 的矩阵.
理解正交矩阵 https://zhuanlan.zhihu.com/p/258464098?utm_source=wechat_session
是正交矩阵，自然满足 $A^T=A^{-1}$

注意:奇异值分解不要求矩阵 $A$ 是方阵

定理 $15.1$ (奇异值分解基本定理）若 $A$ 为一 $\times n$ 实矩阵, $\in \mathbf{R}^{m \times n}$ , 则 $A$
的奇异值分解存在

$\Sigma V^{\mathrm{T}}$

其中 $U$ 是 $m$ 阶正交矩阵, $V$ 是 $n$ 阶正交矩阵, $\Sigma$ 是 $\times n$ 矩形对角矩阵, 其对角线元素非负，且按降序排列。

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

确定 $V$ 和 $\Sigma$
首先构造 $n$ 阶正交实矩阵 $V$ 和 $\times n$ 矩形对角实矩阵 $\Sigma$ 。
矩阵 $A$ 是 $\times n$ 实矩阵, 则矩阵 $A^{\mathrm{T}} A$ 是 $n$ 阶实对称矩阵。因而 $A^{\mathrm{T}} A$ 的特征值都是实数, 并且存在一个 $n$ 阶正交实矩阵 $V$ 实现 $A^{\mathrm{T}} A$ 的对角化, 使得 $V^{\mathrm{T}}\left(A^{\mathrm{T}} A\right) V=\Lambda$ 成立, 其中 $\Lambda$ 是 $n$ 阶对角矩阵, 其对角线元素由 $A^{\mathrm{T}} A$ 的特征值组成。

证明： $A^TA$ 是实对称矩阵
? $(A^TA)^T=A^T(A^T)^T=A^{\mathrm{T}} A$

一个n*n矩阵A可正交对角化的充要条件是A是对称矩阵

$A^TA=V\Lambda V^{-1}==>V^{-1}A^TAV=V^{-1}V\Lambda V^{-1}V==>V^{-1}A^TAV=\Lambda==>V^{T}A^TAV=\Lambda$

而且, $A^{\mathrm{T}} A$ 的特征值都是非负的。事实上, 令 $\lambda$ 是 $A^{\mathrm{T}} A$ 的一个特征值, $x$ 是对应的特征向量, 则
$\|A x\|^{2}=(Ax)^TAx=x^{\mathrm{T}} A^{\mathrm{T}} A x=\lambda x^{\mathrm{T}} x=\lambda\|x\|^{2}$

向量的长度（范数）是非负数 $\|\boldsymbol{v}\|$ ，定义为

$\|\boldsymbol{v}\|=\sqrt{\boldsymbol{v} \cdot \boldsymbol{v}}=\sqrt{v_{1}^{2}+v_{2}^{2}+\cdots+v_{n}^{2}} \quad \text { 且 }\|\boldsymbol{v}\|^{2}=\boldsymbol{v} \cdot \boldsymbol{v}$

而 $\|\boldsymbol{v}\|^{2}=\boldsymbol{v} \cdot \boldsymbol{v}=\boldsymbol{v}^T \boldsymbol{v}$

$A^TAx=\lambda x$

于是
$\lambda=\frac{\|A x\|^{2}}{\|x\|^{2}} \geqslant 0$

可以假设正交矩阵 $V$ 的列的排列使得对应的特征值形成降序排列
$\lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{n} \geqslant 0$

计算特征值的平方根 (实际就是矩阵 $A$ 的奇异值)
$\sigma_{j}=\sqrt{\lambda_{j}}, \quad j=1,2, \cdots, n$

设矩阵 $A$ 的秩是 $\operatorname{rank}(A)=r$ , 则矩阵 $A^{\mathrm{T}} A$ 的秩也是 $r$ 。由于 $A^{\mathrm{T}} A$ 是对称矩阵, 它的秩等于正的特征值的个数, 所以
$\lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{r}>0, \quad \lambda_{r+1}=\lambda_{r+2}=\cdots=\lambda_{n}=0$

对应地有
$\sigma_{1} \geqslant \sigma_{2} \geqslant \cdots \geqslant \sigma_{r}>0, \quad \sigma_{r+1}=\sigma_{r+2}=\cdots=\sigma_{n}=0$

令
$V_{1}=\left[\begin{array}{llll} \nu_{1} & \nu_{2} & \cdots & \left.\nu_{r}\right], \quad V_{2}=\left[\nu_{r+1}\right. & \nu_{r+2} & \cdots & \nu_{n} \end{array}\right].$

其中 $\nu_{1}, \cdots, \nu_{r}$ 为 $A^{\mathrm{T}} A$ 的正特征值对应的特征向量, $\nu_{r+1}, \cdots, \nu_{n}$ 为 0 特征值对应的特征向量, 则
$V=\left[\begin{array}{ll} V_{1} & V_{2} \end{array}\right]$

这就是矩阵 $A$ 的奇异值分解中的 $n$ 阶正交矩阵 $V_{\text {。 }}$
令
$\Sigma_{1}=\left[\begin{array}{cccc} \sigma_{1} & & & \\ & \sigma_{2} & & \\ & & \ddots & \\ & & & \sigma_{r} \end{array}\right]$

则 $\Sigma_{1}$ 是一个 $r$ 阶对角矩阵, 其对角线元素为按降序排列的正的 $\sigma_{1}, \cdots, \sigma_{r}$ , 于是 $\times n$ 矩形对角矩阵 $\Sigma$ 可以表为
$\Sigma=\left[\begin{array}{cc} \Sigma_{1} & 0 \\ 0 & 0 \end{array}\right]$

这就是矩阵 $A$ 的奇异值分解中的 $\times n$ 矩形对角矩阵 $\Sigma_{\text {。 }}$

下面推出后面要用到的一个公式。在式 $V=\left[\begin{array}{ll}V_{1} & V_{2}\end{array}\right]$ 中, $V_{2}$ 的列向量是 $A^{\mathrm{T}} A$ 对应于特征值为 0 的特征向量。因此

$A^{\mathrm{T}} A v_{j}=0, \quad j=r+1, \cdots, n$

于是, $V_{2}$ 的列向量构成了 $A^{\mathrm{T}} A$ 的零空间 $N\left(A^{\mathrm{T}} A\right)$ , 而 $N\left(A^{\mathrm{T}} A\right)=N(A)$ 。所以 $V_{2}$ 的列向量构成 $A$ 的零空间的一组标准正交基。因此，

$A V_{2}=0$

由于 $V$ 是正交矩阵, 由式 $V=\left[\begin{array}{ll}V_{1} & V_{2}\end{array}\right]$ 可得

$\begin{gathered} I=V V^{\mathrm{T}}=V_{1} V_{1}^{\mathrm{T}}+V_{2} V_{2}^{\mathrm{T}} \\ A=A I=A V_{1} V_{1}^{\mathrm{T}}+A V_{2} V_{2}^{\mathrm{T}}=A V_{1} V_{1}^{\mathrm{T}} \end{gathered}$

确定 $U$
接着构造 $m$ 阶正交实矩阵 $U$ 。
令
$\begin{gathered} u_{j}=\frac{1}{\sigma_{j}} A v_{j}, \quad j=1,2, \cdots, r① \\ U_{1}=\left[\begin{array}{llll} u_{1} & u_{2} & \cdots & u_{r} \end{array}\right] \end{gathered}$

则有
$V_{1}=U_{1} \Sigma_{1}$

$V_{1}=A\left[\begin{array}{llll} \nu_{1} & \nu_{2} & \cdots & \left.\nu_{r}\right] \end{array}\right.=\left[\begin{array}{llll} u_{1} & u_{2} & \cdots & u_{r} \end{array}\right]\left[\begin{array}{cccc} \sigma_{1} & & & \\ & \sigma_{2} & & \\ & & \ddots & \\ & & & \sigma_{r} \end{array}\right]= U_{1} \Sigma_{1}$

$U_{1}$ 的列向量构成了一组标准正交集, 因为
$\begin{aligned} u_{i}^{\mathrm{T}} u_{j} &=\left(\frac{1}{\sigma_{i}} v_{i}^{\mathrm{T}} A^{\mathrm{T}}\right)\left(\frac{1}{\sigma_{j}} A v_{j}\right) \\ &=\frac{1}{\sigma_{i} \sigma_{j}} v_{i}^{\mathrm{T}}\left(A^{\mathrm{T}} A v_{j}\right) \\ &=\frac{1}{\sigma_{i} \sigma_{j}} v_{i}^{\mathrm{T}}\left(\sigma_{j}^2 v_{j}\right)\\ &=\frac{\sigma_{j}}{\sigma_{i}} v_{i}^{\mathrm{T}} v_{j} \\ &=\delta_{i j}, \quad i=1,2, \cdots, r ; \quad j=1,2, \cdots, r \end{aligned}②$

由式 ①和式② 可知, $u_{1}, u_{2}, \cdots, u_{r}$ 构成 $A$ 的列空间的一组标准正交基, 列空间的维数为 $r_{\circ}$ 如果将 $A$ 看成是从 $\mathbf{R}^{n}$ 到 $\mathbf{R}^{m}$ 的线性变换, 则 $A$ 的列空间和 $A$ 的值域 $R (A)$ 是相同的。因此 $u_{1}, u_{2}, \cdots, u_{r}$ 也是 $R (A)$ 的一组标准正交基。
若 $R(A)^{\perp}$ 表示 $R (A)$ 的正交补, 则有 $R (A)$ 的维数为 $R(A)^{\perp}$ 的维数为 $m ? r$ , 两者的维数之和等于 $m$ 。而且有 $R(A)^{\perp}=N\left(A^{\mathrm{T}}\right)$ 成立。令 $\left\{u_{r+1}, u_{r+2}, \cdots, u_{m}\right\}$ 为 $N\left(A^{\mathrm{T}}\right)$ 的一组标准正交基, 并令
$\begin{aligned} &U_{2}=\left[\begin{array}{llll} u_{r+1} & u_{r+2} & \cdots & u_{m} \end{array}\right] \\ &U=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right] \end{aligned}$

则 $u_{1}, u_{2}, \cdots, u_{m}$ 构成了 $\mathbf{R}^{m}$ 的一组标准正交基。因此, $U$ 是 $m$ 阶正交矩阵, 这就是矩阵 $A$ 的奇异值分解中的 $m$ 阶正交矩阵。
(3) 证明 $\Sigma V^{\mathrm{T}}=A$

$\begin{aligned} U \Sigma V^{\mathrm{T}} &=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right]\left[\begin{array}{cc} \Sigma_{1} & 0 \\ 0 & 0 \end{array}\right]\left[\begin{array}{c} V_{1}^{\mathrm{T}} \\ V_{2}^{\mathrm{T}} \end{array}\right] \\ &=U_{1} \Sigma_{1} V_{1}^{\mathrm{T}} \\ &=A V_{1} V_{1}^{\mathrm{T}} \\ &=A \end{aligned}$

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

15.1.2 紧奇异值分解与截断奇异值分解

紧奇异值分解
定义 $15.2$ 设有 $\times n$ 实矩阵 $A$ , 其秩为 $\operatorname{rank}(A)=r, r \leqslant \min (m, n)$ , 则称 $U_{r} \Sigma_{r} V_{r}^{\mathrm{T}}$ 为 $A$ 的紧奇异值分解 ( compact singular value decomposition ), 即

$\begin{aligned} &A=U_{r} \Sigma_{r} V_{r}^{\mathrm{T}} \end{aligned}$

其中 $U_{r}$ 是 $\times r$ 矩阵, $V_{r}$ 是 $\times r$ 矩阵, $\Sigma_{r}$ 是 $r$ 阶对角矩阵; 矩阵 $U_{r}$ 由完全奇异值分解中 $U$ 的前 $r$ 列、矩阵 $V_{r}$ 由 $V$ 的前 $r$ 列、矩阵 $\Sigma_{r}$ 由 $\Sigma$ 的前 $r$ 个对角线元素得到。紧奇异值分解的对角矩阵 $\Sigma_{r}$ 的秩与原始矩阵 $A$ 的秩相等。
截断奇异值分解
在矩阵的奇异值分解中, 只取最大的 $k$ 个奇异值 $(k < r, r$ 为矩阵的秩）对应的部分, 就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时, 通常指截断奇异值分解。
定义 $15.3$ 设 $A$ 为 $\times n$ 实矩阵, 其秩 $\operatorname{rank}(A)=r$ , 且 $0 < k < r$ , 则称 $U_{k} \Sigma_{k} V_{k}^{\mathrm{T}}$ 为矩阵 $A$ 的截断奇异值分解 ( truncated singular value decomposition )
$\approx U_{k} \Sigma_{k} V_{k}^{\mathrm{T}}$

其中 $U_{k}$ 是 $\times k$ 矩阵, $V_{k}$ 是 $\times k$ 矩阵, $\Sigma_{k}$ 是 $k$ 阶对角矩阵; 矩阵 $U_{k}$ 由完全奇异值分解中 $U$ 的前 $k$ 列、矩阵 $V_{k}$ 由 $V$ 的前 $k$ 列、矩阵 $\Sigma_{k}$ 由 $\Sigma$ 的前 $k$ 个对角线元素得到。对角矩阵 $\Sigma_{k}$ 的秩比原始矩阵 $A$ 的秩低。

紧奇异值分解对应着无损压缩
截断奇异值分解对应着有损压缩。

15.1.3 几何解释

任意一个向量 $\in \mathbf{R}^{n}$ , 经过基于 $\Sigma V^{\mathrm{T}}$ 的线性变换，等价于经过坐标系的旋转或反射变换 $V^{\mathrm{T}}$ , 坐标轴的缩放变换 $\Sigma$ , 以及坐标系的旋转或反射变换 $U$ , 得到向量 $\in \mathbf{R}^{m}$ 。

在这里插入图片描述

15.1.4 主要性质

设矩阵 $A$ 的奇异值分解为 $\Sigma V^{\mathrm{T}}$ , 则以下关系成立:
$\begin{aligned} &A^{\mathrm{T}} A=\left(U \Sigma V^{\mathrm{T}}\right)^{\mathrm{T}}\left(U \Sigma V^{\mathrm{T}}\right)=V\left(\Sigma^{\mathrm{T}} \Sigma\right) V^{\mathrm{T}} \\ &A A^{\mathrm{T}}=\left(U \Sigma V^{\mathrm{T}}\right)\left(U \Sigma V^{\mathrm{T}}\right)^{\mathrm{T}}=U\left(\Sigma \Sigma^{\mathrm{T}}\right) U^{\mathrm{T}} \end{aligned}$

矩阵 $A^{\mathrm{T}} A$ 和 $A^{\mathrm{T}}$ 的特征分解存在, 且可以由矩阵 $A$ 的奇异值分解的矩阵表示。 $V$ 的列向量是 $A^{\mathrm{T}} A$ 的特征向量, $U$ 的列向量是 $A^{\mathrm{T}}$ 的特征向量, $\Sigma$ 的奇异值是 $A^{\mathrm{T}} A$ 和 $A^{\mathrm{T}}$ 的特征值的平方根。
在矩阵 $A$ 的奇异值分解中, 奇异值、左奇异向量和右奇异向量之间存在对应关系。
由 $\Sigma V^{\mathrm{T}}$ 易知
$\Sigma$

比较这一等式两端的第 $j$ 列, 得到
$v_{j}=\sigma_{j} u_{j}, \quad j=1,2, \cdots, n$

这是矩阵 $A$ 的右奇异向量和奇异值、左奇异向量的关系。
类似地, 由
$A^{\mathrm{T}} U=V \Sigma^{\mathrm{T}}$

得到
$\begin{gathered} A^{\mathrm{T}} u_{j}=\sigma_{j} v_{j}, \quad j=1,2, \cdots, n \\ A^{\mathrm{T}} u_{j}=0, \quad j=n+1, n+2, \cdots, m \end{gathered}$

这是矩阵 $A$ 的左奇异向量和奇异值、右奇异向量的关系。
矩阵 $A$ 的奇异值分解中, 奇异值 $\sigma_{1}, \sigma_{2}, \cdots, \sigma_{n}$ 是唯一的, 而矩阵 $U$ 和 $V$ 不是唯一的。
矩阵 $A$ 和 $\Sigma$ 的秩相等, 等于正奇异值 $\sigma_{i}$ 的个数 $r$ (包含重复的奇异值)。
矩阵 $A$ 的 $r$ 个右奇异向量 $v_{1}, v_{2}, \cdots, v_{r}$ 构成 $A^{\mathrm{T}}$ 的值域 $R\left(A^{\mathrm{T}}\right)$ 的一组标准正交基。因为矩阵 $A^{\mathrm{T}}$ 是从 $\mathbf{R}^{m}$ 映射到 $\mathbf{R}^{n}$ 的线性变换，则 $A^{\mathrm{T}}$ 的值域 $R\left(A^{\mathrm{T}}\right)$ 和 $A^{\mathrm{T}}$ 的列空间是相同的, $v_{1}, v_{2}, \cdots, v_{r}$ 是 $A^{\mathrm{T}}$ 的一组标准正交基, 因而也是 $R\left(A^{\mathrm{T}}\right)$ 的一组标准正交基。
矩阵 $A$ 的 $n ? r$ 个右奇异向量 $v_{r+1}, v_{r+2}, \cdots, v_{n}$ 构成 $A$ 的零空间 $N (A)$ 的一组标准正交基。
矩阵 $A$ 的 $r$ 个左奇异向量 $u_{1}, u_{2}, \cdots, u_{r}$ 构成值域 $R (A)$ 的一组标准正交基。矩阵 $A$ 的 $m ? r$ 个左奇异向量 $u_{r+1}, u_{r+2}, \cdots, u_{m}$ 构成 $A^{\mathrm{T}}$ 的零空间 $N\left(A^{\mathrm{T}}\right)$ 的一组标准正交基。

15.2 奇异值分解的计算

矩阵奇异值分解的计算过程
给定 $\times n$ 矩阵 $A$

首先求 $A^{\mathrm{T}} A$ 的特征值和特征向量。
计算对称矩阵 $W=A^{\mathrm{T}} A$ 。
求解特征方程
$(W-\lambda I) x=0$

得到特征值 $\lambda_{i}$ , 并将特征值由大到小排列
$\lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{n} \geqslant 0$

将特征值 $\lambda_{i}(i=1,2, \cdots, n)$ 代入特征方程求得对应的特征向量。
求 $n$ 阶正交矩阵 $V$
将特征向量单位化, 得到单位特征向量 $v_{1}, v_{2}, \cdots, v_{n}$ , 构成 $n$ 阶正交矩阵 $V$ :
$V=\left[\begin{array}{llll} v_{1} & v_{2} & \cdots & v_{n} \end{array}\right]$
求 $\times n$ 对角矩阵 $\Sigma$
计算 $A$ 的奇异值
$\sigma_{i}=\sqrt{\lambda_{i}}, \quad i=1,2, \cdots, n$

构造 $\times n$ 矩形对角矩阵 $\Sigma$ , 主对角线元素是奇异值, 其余元素是零,
$\Sigma=\operatorname{diag}\left(\sigma_{1}, \sigma_{2}, \cdots, \sigma_{n}\right)$
求 $m$ 阶正交矩阵 $U$
对 $A$ 的前 $r$ 个正奇异值, 令
$u_{j}=\frac{1}{\sigma_{j}} A v_{j}, \quad j=1,2, \cdots, r$

得到
$U_{1}=\left[\begin{array}{llll} u_{1} & u_{2} & \cdots & u_{r} \end{array}\right]$

求 $A^{\mathrm{T}}$ 的零空间的一组标准正交基 $\left\{u_{r+1}, u_{r+2}, \cdots, u_{m}\right\}$ , 令
$U_{2}=\left[\begin{array}{llll} u_{r+1} & u_{r+2} & \cdots & u_{m} \end{array}\right]$

并令
$U=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right]$
得到奇异值分解
$\Sigma V^{\mathrm{T}}$

15.3 奇异值分解与矩阵近似

15.3.1 弗罗贝尼乌斯范数

定义 $15.4$ (弗罗贝尼乌斯范数）设矩阵 $\in \mathbf{R}^{m \times n}, A=\left[a_{i j}\right]_{m \times n}$ , 定义矩阵 $A$ 的弗罗贝尼乌斯范数为

$\|A\|_{F}=\left(\sum_{i=1}^{m} \sum_{j=1}^{n}\left(a_{i j}\right)^{2}\right)^{\frac{1}{2}}$

引理 $15.1$ 设矩阵 $\in \mathbf{R}^{m \times n}, A$ 的奇异值分解为 $\Sigma V^{\mathrm{T}}$ , 其中 $\Sigma=\operatorname{diag}\left(\sigma_{1},\right.$ ,
$\left.\sigma_{2}, \cdots, \sigma_{n}\right)$ , 则

$\|A\|_{F}=\left(\sigma_{1}^{2}+\sigma_{2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}$

证明一般地, 若 $Q$ 是 $m$ 阶正交矩阵, 则有

$Q A\|_{F}=\|A\|_{F}$

因为

$\begin{aligned} \|Q A\|_{F}^{2} &=\left\|\left(Q a_{1}, Q a_{2}, \cdots, Q a_{n}\right)\right\|_{F}^{2} \\ &=\sum_{i=1}^{n}\left\|Q a_{i}\right\|_{2}^{2}=\sum_{i=1}^{n}(Q a_{i})^TQ a_{i}=\sum_{i=1}^{n}a_{i}^TQ^TQ a_{i}=\sum_{i=1}^{n}\left\|a_{i}\right\|_{2}^{2}=\|A\|_{F}^{2} \end{aligned}$

同样, 若 $P$ 是 $n$ 阶正交矩阵, 则有

$\left\|A P^{\mathrm{T}}\right\|_{F}=\|A\|_{F}$

故

$\|A\|_{F}=\left\|U \Sigma V^{\mathrm{T}}\right\|_{F}=\|\Sigma\|_{F}$

即

$\|A\|_{F}=\left(\sigma_{1}^{2}+\sigma_{2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}$

15.3.2 矩阵的最优近似

定理 $15.2$ 设矩阵 $\in \mathbf{R}^{m \times n}$ , 矩阵的秩 $\operatorname{rank}(A)=r$ , 并设 $\mathcal{M}$ 为 $\mathbf{R}^{m \times n}$ 中所
有秩不超过 $k$ 的矩阵集合, $0 < k < r$ , 则存在一个秩为 $k$ 的矩阵 $\in \mathcal{M}$ , 使得

$\|A-X\|_{F}=\min _{S \in \mathcal{M}}\|A-S\|_{F}$

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

定理 $15.3$ 设矩阵 $\in \mathbf{R}^{m \times n}$ , 矩阵的秩 $\operatorname{rank}(A)=r$ , 有奇异值分解 $A =$ $\Sigma V^{\mathrm{T}}$ , 并设 $\mathcal{M}$ 为 $\mathrm{R}^{m \times n}$ 中所有秩不超过 $k$ 的矩阵的集合, $0 < k < r$ , 若秩为 $k$ 的矩阵 $\in \mathcal{M}$ 满足

$\|A-X\|_{F}=\min _{S \in \mathcal{M}}\|A-S\|_{F}②$

则

$\|A-X\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}①$

特别地, 若 $A^{\prime}=U \Sigma^{\prime} V^{\mathrm{T}}$ , 其中

$\Sigma^{\prime}=\left[\begin{array}{ccccc} \sigma_{1} & & & & \\ & \ddots & & & 0 & \\ & & \sigma_{k} & & & \\ & & & 0 & & \\ & 0 & & & \ddots & \\ & & & & & 0 \end{array}\right]=\left[\begin{array}{cc} \Sigma_{k} & 0 \\ 0 & 0 \end{array}\right]$

$A-A^{\prime}=U\left[\begin{array}{cc} 0 & 0 \\ 0 & \Sigma_{n-k} \end{array}\right]V^T$

则

$\left\|A-A^{\prime}\right\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}=\min _{S \in \mathcal{M}}\|A-S\|_{F}$

证明令 $\in \mathcal{M}$ 为满足式 $②$ 的一个矩阵。由于

$\|A-X\|_{F} \leqslant\left\|A-A^{\prime}\right\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}③$

下面证明

$\|A-X\|_{F} \geqslant\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}$

于是式 ①成立。

设 $X$ 的奇异值分解为 $\Omega P^{\mathrm{T}}$ , 其中
若令矩阵 $B=Q^{\mathrm{T}} A P$ , 则 $P^{\mathrm{T}}$ 。由此得到

$\|A-X\|_{F}=\left\|Q(B-\Omega) P^{\mathrm{T}}\right\|_{F}=\|B-\Omega\|_{F}$

用 $\Omega$ 分块方法对 $B$ 分块

$B=\left[\begin{array}{ll} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}\right]$

其中 $B_{11}$ 是 $\times k$ 子矩阵, $B_{12}$ 是 $\times(n-k)$ 子矩阵, $B_{21}$ 是 $\times k$ 子矩阵, $B_{22}$ 是 $\times(n-k)$ 子矩阵。可得

$\begin{aligned} \|A-X\|_{F}^{2} &=\|B-\Omega\|_{F}^{2} \\ &=\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}+\left\|B_{12}\right\|_{F}^{2}+\left\|B_{21}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2} \end{aligned}$

现证 $B_{12}=0, B_{21}=0$ 。用反证法。若 $B_{12} \neq 0$ , 令

$Y=Q\left[\begin{array}{cc} B_{11} & B_{12} \\ 0 & 0 \end{array}\right] P^{\mathrm{T}}$

则 $\in \mathcal{M}$ , 且

$\|A-Y\|_{F}^{2}=\left\|B_{21}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2}<\|A-X\|_{F}^{2}$

这与 $X$ 的定义式 $③$ 矛盾, 证明了 $B_{12}=0$ 。同样可证 $B_{21}=0$ 。于是

$\|A-X\|_{F}^{2}=\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2}$

再证 $B_{11}=\Omega_{k}$ 。为此令

$Z=Q\left[\begin{array}{cc} B_{11} & 0 \\ 0 & 0 \end{array}\right] P^{\mathrm{T}}$

则 $\in \mathcal{M}$ , 且

$\|A-Z\|_{F}^{2}=\left\|B_{22}\right\|_{F}^{2} \leqslant\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2}=\|A-X\|_{F}^{2}$

由式③知, $\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}=0$ , 即 $B_{11}=\Omega_{k}$ 。
最后看 $B_{22}$ 。若 $\times(n-k)$ 子矩阵 $B_{22}$ 有奇异值分解 $U_{1} \Lambda V_{1}^{\mathrm{T}}$ , 则

$\|A-X\|_{F}=\left\|B_{22}\right\|_{F}=\|\Lambda\|_{F}$

证明 $\Lambda$ 的对角线元素为 $A$ 的奇异值。为此, 令

$U_{2}=\left[\begin{array}{cc} I_{k} & 0 \\ 0 & U_{1} \end{array}\right], \quad V_{2}=\left[\begin{array}{cc} I_{k} & 0 \\ 0 & V_{1} \end{array}\right]$

其中 $I_{k}$ 是 $k$ 阶单位矩阵, $U_{2}, V_{2}$ 的分块与 $B$ 的分块一致。注意到 $B$ 及 $B_{22}$ 的奇异值分解，即得

$U_{2}^{\mathrm{T}} Q^{\mathrm{T}} A P V_{2}=\left[\begin{array}{cc} \Omega_{k} & 0 \\ 0 & \Lambda \end{array}\right]$

$A=\left(Q U_{2}\right)\left[\begin{array}{cc} \Omega_{k} & 0 \\ 0 & \Lambda \end{array}\right]\left(P V_{2}\right)^{\mathrm{T}}$

由此可知 $\Lambda$ 的对角线元素为 $A$ 的奇异值。故有

$\|A-X\|_{F}=\|\Lambda\|_{F} \geqslant\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}$

于是证明了

$\|A-X\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}=\left\|A-A^{\prime}\right\|_{F}$

15.3.3 矩阵的外积展开式

下面介绍利用外积展开式对矩阵 $A$ 的近似。矩阵 $A$ 的奇异值分解 $\Sigma V^{\mathrm{T}}$ 也可以由外积形式表示。事实上, 若将 $A$ 的奇异值分解看成矩阵 $\Sigma$ 和 $V^{\mathrm{T}}$ 的乘积, 将 $\Sigma$ 按列向量分块, 将 $V^{\mathrm{T}}$ 按行向量分块, 即得

$\begin{gathered} U \Sigma=\left[\begin{array}{llll} \sigma_{1} u_{1} & \sigma_{2} u_{2} & \cdots & \sigma_{n} u_{n} \end{array}\right] \\ V^{\mathrm{T}}=\left[\begin{array}{c} v_{1}^{\mathrm{T}} \\ v_{2}^{\mathrm{T}} \\ \vdots \\ v_{n}^{\mathrm{T}} \end{array}\right] \end{gathered}$

则

$A=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n} u_{n} v_{n}^{\mathrm{T}}$

上式称为矩阵 $A$ 的外积展开式, 其中 $u_{k} v_{k}^{\mathrm{T}}$ 为 $\times n$ 矩阵, 是列向量 $u_{k}$ 和行向量 $v_{k}^{\mathrm{T}}$ 的外积, 其第 $i$ 行第 $j$ 列元素为 $u_{k}$ 的第 $i$ 个元素与 $v_{k}^{\mathrm{T}}$ 的第 $j$ 个元素的乘积。即

$u_{i} v_{j}^{\mathrm{T}}=\left[\begin{array}{c} u_{1 i} \\ u_{2 i} \\ \vdots \\ u_{m i} \end{array}\right]\left[\begin{array}{llll} v_{1 j} & v_{2 j} & \cdots & v_{n j} \end{array}\right]=\left[\begin{array}{cccc} u_{1 i} v_{1 j} & u_{1 i} v_{2 j} & \cdots & u_{1 i} v_{n j} \\ u_{2 i} v_{1 j} & u_{2 i} v_{2 j} & \cdots & u_{2 i} v_{n j} \\ \vdots & \vdots & & \vdots \\ u_{m i} v_{1 j} & u_{m i} v_{2 j} & \cdots & u_{m i} v_{n j} \end{array}\right]$

$A$ 的外积展开式也可以写成下面的形式

$A=\sum_{k=1}^{n} A_{k}=\sum_{k=1}^{n} \sigma_{k} u_{k} v_{k}^{\mathrm{T}}$

其中 $A_{k}=\sigma_{k} u_{k} v_{k}^{\mathrm{T}}$ 是 $\times n$ 矩阵。上式将矩阵 $A$ 分解为矩阵的有序加权和。
由矩阵 $A$ 的外积展开式知, 若 $A$ 的秩为 $n$ , 则

$A=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n} u_{n} v_{n}^{\mathrm{T}}$

设矩阵

$A_{n-1}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n-1} u_{n-1} v_{n-1}^{\mathrm{T}}$

则 $A_{n-1}$ 的秩为 $n ? 1$ , 并且 $A_{n-1}$ 是秩为 $n ? 1$ 矩阵在弗罗贝尼乌斯范数意义下 $A$ 的最优近似矩阵。
类似地, 设矩阵

$A_{n-2}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n-2} u_{n-2} v_{n-2}^{\mathrm{T}}$

则 $A_{n-2}$ 的秩为 $n ? 2$ , 并且 $A_{n-2}$ 是秩为 $n ? 2$ 矩阵中在弗罗贝尼乌斯范数意义下 $A$ 的最优近似矩阵。以此类推。一般地，设矩阵

$A_{k}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{k} u_{k} v_{k}^{\mathrm{T}}$

则 $A_{k}$ 的秩为 $k$ , 并且 $A_{k}$ 是秩为 $k$ 的矩阵中在弗罗贝尼乌斯范数意义下 $A$ 的最优近似矩阵。矩阵 $A_{k}$ 就是 $A$ 的截断奇异值分解。
由于通常奇异值 $\sigma_{i}$ 递减很快, 所以 $k$ 取很小值时, $A_{k}$ 也可以对 $A$ 有很好的近似。