奇异值分解、伪逆与低秩近似

特征分解主要研究方阵。奇异值分解适用于任意 $m\times n$ 矩阵，并且使用定义域与陪域中各自的正交基描述同一个线性映射。

两端正交换基，中间沿坐标方向缩放

对任意实矩阵 $A$，存在正交矩阵 $U,V$ 与非负对角形矩阵 $\Sigma$，使

$$A=U\Sigma V^{\mathsf T}.$$

$V^{\mathsf T}$ 把输入换到右奇异向量基，$\Sigma$ 沿互相垂直的方向缩放，$U$ 再把结果放入输出空间。非零对角元素

$$\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0$$

称为奇异值，个数 $r$ 等于 $\operatorname{rank}(A)$。

先核对矩形分解的大小

完整 SVD 中，$U$ 为 $m\times m$，$\Sigma$ 为 $m\times n$，$V$ 为 $n\times n$。只保留非零模式则得到紧致分解 $A=U_r\Sigma_rV_r^{\mathsf T}$，两端分别只有 $r$ 列。正交变换可能包含反射，因此不能把 $U,V$ 一概称为旋转。

奇异值来自两个对称矩阵

$A^{\mathsf T}A$ 是半正定对称矩阵。谱定理给出

$$A^{\mathsf T}A\mathbf v_i=\sigma_i^2\mathbf v_i.$$

对 $\sigma_i>0$，定义 $\mathbf u_i=A\mathbf v_i/\sigma_i$。这些 $\mathbf u_i$ 两两正交，并满足 $A\mathbf v_i=\sigma_i\mathbf u_i$。补齐两端的正交基就得到完整 SVD。

特征值可能为负数或复数，奇异值总是非负实数。方阵不可对角化也不妨碍 SVD 存在。

转置直接验证对称性，而 $\mathbf z^{\mathsf T}A^{\mathsf T}A\mathbf z=\|A\mathbf z\|^2\ge0$ 验证半正定性。补全两端的基后，把每个 $\mathbf v_i$ 上的等式合并，得到 $AV=U\Sigma$；右乘 $V^{\mathsf T}$ 即得分解。可逆换基不改变像的维数，$\Sigma$ 又恰有 $r$ 个独立的非零列，所以秩为 $r$。当 $r=0$ 时 $A=0$，任意正交基都适用。

为什么构造出的左向量正交

对于正奇异值，

$$\mathbf u_i^{\mathsf T}\mathbf u_j =\frac{\mathbf v_i^{\mathsf T}A^{\mathsf T}A\mathbf v_j}{\sigma_i\sigma_j} =\frac{\sigma_j^2}{\sigma_i\sigma_j}\delta_{ij} =\delta_{ij}.$$

零特征值对应的 $\mathbf v$ 满足 $\|A\mathbf v\|^2=0$，因此 $A\mathbf v=0$。这补齐了从谱定理到 SVD 的两种情况。

四个基本子空间在 SVD 中对齐

非零右奇异向量张成行空间，零奇异值对应的右奇异向量张成 $\ker A$。非零左奇异向量张成列空间，其余左奇异向量张成 $\ker A^{\mathsf T}$。因此

$$\operatorname{row}(A)=(\ker A)^\perp, \qquad \operatorname{col}(A)=(\ker A^{\mathsf T})^\perp.$$

这把向量空间章节中分别计算的行、列与零空间放进同一个正交结构。

证明

写 $\mathbf x=\sum_i y_i\mathbf v_i$，则 $A\mathbf x=\sum_{i\le r}\sigma_i y_i\mathbf u_i$。由正交性，它为零当且仅当 $y_1=\cdots=y_r=0$；像也恰好由 $\mathbf u_1,\ldots,\mathbf u_r$ 张成。对 $A^{\mathsf T}=V\Sigma^{\mathsf T}U^{\mathsf T}$ 重复同一论证，即得转置的核与像。行空间就是 $A^{\mathsf T}$ 的像，两个正交补等式随之成立。

伪逆统一精确解与最小二乘解

把每个非零奇异值取倒数，得到 $\Sigma^+$。Moore–Penrose 伪逆为

$$A^+=V\Sigma^+U^{\mathsf T}.$$

$\widehat{\mathbf x}=A^+\mathbf b$ 给出最小二乘解中范数最小的那一个。若系统一致，它是在全部精确解中长度最小的解；若 $A$ 可逆，则 $A^+=A^{-1}$。

小奇异值会把数据误差放大约 $1/\sigma_i$ 倍。截断极小奇异值会牺牲一部分拟合能力，以换取稳定性。

伪逆最小范数性质的一般证明

设完整 SVD 为 $A=U\Sigma V^{\mathsf T}$，令 $\mathbf y=V^{\mathsf T}\mathbf x$、$\mathbf c=U^{\mathsf T}\mathbf b$。正交矩阵保持范数，所以

$$\|A\mathbf x-\mathbf b\|^2 =\sum_{i=1}^r(\sigma_i y_i-c_i)^2+\sum_{i=r+1}^m c_i^2.$$

后一个和与输入无关。前一个和的每项都可以独立变成零，要求 $y_i=c_i/\sigma_i$。其余 $n-r$ 个输入坐标任意，恰好对应零空间。又因为 $\|\mathbf x\|^2=\sum_i y_i^2$，把所有自由坐标取零才得到唯一最小范数。这正是 $V\Sigma^+U^{\mathsf T}\mathbf b$。

一个非方阵的全部解

取单行矩阵 $A=(1\ \ 1)$。紧致 SVD 可以取 $U_r=(1)$、$\Sigma_r=(\sqrt2)$、$V_r=(1,1)^{\mathsf T}/\sqrt2$。于是

$$A^+=\begin{pmatrix}1/2\\1/2\end{pmatrix}.$$

对右端 $b=2$，伪逆给出 $(1,1)$。全部精确解为 $(1+t,1-t)$，平方长度为 $2+2t^2$，所以伪逆确实选出了唯一最短解。

截断 SVD 给出最佳低秩近似

把 SVD 写成外积和：

$$A=\sum_{i=1}^r\sigma_i\mathbf u_i\mathbf v_i^{\mathsf T}.$$

只保留前 $k$ 项得到 $A_k$。Eckart–Young 定理说明，在二范数或 Frobenius 范数下，$A_k$ 是所有秩不超过 $k$ 的矩阵中最接近 $A$ 的一个。误差由被舍弃的奇异值精确控制。

低秩误差与 PCA 的精确含义

矩阵二范数是单位输入可能产生的最大输出长度，Frobenius 范数是所有条目平方和的平方根。对 $0\le k<r$，截断误差为

$$\|A-A_k\|_2=\sigma_{k+1}, \qquad \|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2.$$

二范数最优性可直接证明：任意秩不超过 $k$ 的矩阵 $B$，在前 $k+1$ 个右奇异向量的张成空间里必有单位向量 $\mathbf z$ 满足 $B\mathbf z=0$。于是 $\|(A-B)\mathbf z\|=\|A\mathbf z\|\ge\sigma_{k+1}$；截断矩阵达到此下界。

误差公式也可直接验证：把单位输入按右奇异基展开，经过 $A-A_k$ 后长度平方为 $\sum_{i>k}\sigma_i^2y_i^2\le\sigma_{k+1}^2$，在 $\mathbf v_{k+1}$ 处取等号。对于 Frobenius 范数，左乘正交矩阵保持每列长度，右乘正交矩阵保持每行长度，故都保持全部元素的平方和；计算便归结为 $\Sigma$ 中删去的对角元平方和。

Frobenius 范数下的低秩最优性证明

设 $B$ 的列空间为 $W$，维数不超过 $k$，正交投影记为 $P$。逐列使用勾股分解，得到

$$\|A-B\|_F^2 =\|(I-P)A\|_F^2+\|PA-B\|_F^2 \ge\|A\|_F^2-\|PA\|_F^2.$$

写 $\alpha_i=\|P\mathbf u_i\|^2$，其中 $\mathbf u_i$ 是完整左奇异向量基。则 $0\le\alpha_i\le1$，且 $\sum_i\alpha_i=\dim W\le k$：将 $P$ 写成 $W$ 的正交归一基外积和，再对完整基求和即可验证。由外积和的正交性，

$$\|PA\|_F^2=\sum_{i=1}^r\sigma_i^2\alpha_i \le\sum_{i=1}^k\sigma_i^2.$$

最后一个不等式是把不超过 $k$ 的总权重优先分配给最大的系数：若较小系数仍有权重而较大系数未满，把权重向前移动不会减小总和。因此任何 $B$ 的误差至少为 $\sum_{i>k}\sigma_i^2$。截断 SVD 达到这个下界。$k\ge r$ 时直接取 $B=A$，误差为零。

PCA 还需要先说明数据怎样中心化

把每个样本减去样本均值后组成数据矩阵，右奇异向量给出主要变化方向，奇异值平方与各方向的方差成比例。均值与方差概念可参考期望和方差。若各特征单位差异很大，还要说明是否标准化，否则数值尺度可能主导主成分。

PCA 中明确把 $N$ 个样本放成行，中心化矩阵为 $X\in\mathbb R^{N\times d}$，且 $N>1$。样本协方差为

$$C=\frac{X^{\mathsf T}X}{N-1} =V\frac{\Sigma^{\mathsf T}\Sigma}{N-1}V^{\mathsf T}.$$

所以主方向是右奇异向量，方差是 $\sigma_i^2/(N-1)$。若把样本改放成列，左右奇异向量的角色也随之交换。

沿单位特征方向 $\mathbf v$ 投影，样本列为 $X\mathbf v$，均值为零，样本方差为 $\|X\mathbf v\|^2/(N-1)=\mathbf v^{\mathsf T}C\mathbf v$。Rayleigh 商的界说明最大方差在第一右奇异向量处取得；限制到它的正交补后重复论证，便得到后续主方向。若特征值重复，相应特征空间内任取正交归一基都可以。

练习

练习一个秩一矩阵

说明 $A=\begin{pmatrix}1&2\\2&4\end{pmatrix}$ 只有一个非零奇异值。

解答

第二列是第一列的两倍，所以秩为一。非零奇异值的数量等于秩，因此只有一个。

练习可逆矩阵的伪逆

从 SVD 说明可逆方阵满足 $A^+=A^{-1}$。

解答

可逆时所有奇异值非零，$A^+=V\Sigma^{-1}U^{\mathsf T}$，而 $(U\Sigma V^{\mathsf T})^{-1}=V\Sigma^{-1}U^{\mathsf T}$。

练习截断后的误差

若奇异值为 $5,2,0.1$，最佳秩一近似在二范数下的误差是多少？

解答

二范数误差等于第一个被舍弃的奇异值，即 $2$。