动机
两个相同的列把同一效果描述了两次。拟合问题可以决定两个系数的和,却不能决定这个和应怎样分配。任选一种分配可能是有效的最小二乘答案,但不能称它为唯一答案。最小范数规则增加第二个明确决定:在所有最佳拟合中,选取指定坐标下最短的系数向量。
微小奇异值带来另一种困难。它在精确算术中非零,因此系数仍被决定;但极小的数据改动可使该系数大幅变动。当数据无法分辨这个方向时,舍弃它可以合理。然而这一步改变了模型,并非用代数证明原矩阵的秩较小。
本节从奇异值分解推导这两个决定,涵盖长方形及零秩情况。先前 QR 单元假设满列秩。
定义
定义 15.1.1
(奇异值分解)
设 、,秩为 。一个完整的奇异值分解为
其中 、 正交。长方形对角矩阵 有上述 个正元素,其余为零。 分别是 的列向量。
定义 15.1.2
(伪逆与最小范数最小二乘解)
Moore–Penrose 伪逆定义为
若 ,两个和都是空和,故 、。行空间为 ,零空间为 。最小二乘解在所有 中最小化 ;最小范数解则在整个最小二乘解集合中最小化 。这是两阶段优化,并非对固定正数 最小化 的同一目标。
定义 15.1.3
(阈值秩与截断解)
给定明确的绝对阈值 ,定义
严格不等式指定了恰好等于阈值时如何处理。相对阈值如 ,或按测量不确定性、舍入预算制定的阈值,都需要明确说明其意义。没有一个阈值能普遍适用于所有单位和噪声尺度。
定理/命题
定理 15.1.4
(全部最小二乘解与唯一最短解)
对每个实长方形矩阵 及每个 ,全部最小二乘解为
其拟合向量及残差唯一:
唯一最小范数解是 ,其范数平方为
不加“最小范数”限制时,最小二乘系数向量唯一,当且仅当 ,亦即 满列秩。解的存在不要求满秩,也不要求方程相容。
定理 15.1.5
(奇异值截断保证了什么)
令 ,必要时把奇异值序列补零,则截断给出
其中保留全部正奇异值时令 。若 ,则
是 的唯一最小范数最小二乘解,亦是把原矩阵 的系数限制在 后的唯一残差极小者。它未必在原来所有系数向量中最小化残差。若 ,则 、。
证明思路或证明
为何 SVD 存在
证明
(由 的谱定理得出存在性)
实对称谱定理适用于 。因 ,其特征值非负。选取标准正交特征基 ,把正特征值 排在前面。由 得 ,再由秩与零度定理可知恰有 个正特征值。对每个正值令 ,则
若 对应零特征值,则 ,所以 。把已有的 扩充成 的标准正交基。将任意向量按 展开,即证 。这里以对称谱定理为先备知识,给出存在性证明,并非建议借形成 计算 SVD。形成该矩阵可使条件数平方,亦可能因舍入而抹去微小方向。
重复奇异值容许在相应子空间内选取不同标准正交基。因此个别奇异向量可以不唯一,但下述映射和投影保持相同。
分开能拟合与不能拟合的方向
证明
(奇异向量坐标下的最小二乘解)
写 、。由正交不变性,
第二个和与 无关。取 可令第一个和的每项为零。其余 个 坐标可任意选取,正好对应 。变换回去便证明全部极小者的形式及最优残差公式。
同时,
最后一个和的唯一最小值为零,故最小范数解存在且唯一,也包括 。等价地, 与零空间正交,因此每个 都满足 。三角求解返回一个看来较短的答案,仍必须符合此正交条件;把自由变量设为零并不足够。
直接相乘得
这两者是投影到列空间及行空间的对称正交投影。因此 、、、。这四个恒等式刻画 Moore–Penrose 伪逆。为证唯一性,设另一矩阵 亦满足它们。则 对称且幂等,值域包含于 ,并因 而固定每个 ,故 就是同一正交投影 。同样, 对称且幂等,并满足 :一个方向直接成立,而 推出 。因此 投影到行空间。由 ,每个 都在行空间内,且满足 。先前已证行空间内原像唯一,故每个 都有 ,即 。这也证明结果不依赖奇异向量基的选择。
补充而言,即使秩不足,正规方程 仍是最小二乘的充要条件。把 的残差平方展开,若正规方程成立,交叉项为零,目标只增加 。反之,若某方向交叉项非零,沿合适符号作足够小位移便可减少目标。正规方程刻画整个仿射解族,并不选出最短成员。
证明透视
两种唯一性位于不同空间
决定性的一步是正交变量替换 、。选择它,是因为两阶段问题的两个目标同时变得可分离: 正交保持残差范数, 正交保持系数范数,而 把每个 只与一个 联系起来。证明没有用到任何秩或相容性假设;正奇异值只用于对 解出 。
两种唯一性来自不同的坐标。拟合唯一,因为坐标 被迫取定,这正是 到列空间的正交投影唯一。系数不唯一,因为 完全不进入残差;它们参数化 。只有第二个目标,即系数范数,迫使它们为零;而且这是唯一的,因为它们的贡献是平方和 。把列空间(拟合所在)与行空间及零空间(系数所在)分开,便不会把正确的投影唯一性论证误用为系数唯一性论证。
截断与最佳低秩近似
证明
(截断公式与秩 下界)
在奇异向量坐标下, 在被舍弃方向上是对角作用,谱范数就是最大的被舍弃奇异值。每个保留方向的系数 精确重现 ;其余残差坐标保持为 。这证明截断公式、系数界及限制空间上的残差极小化,而没有声称被舍弃方向在原数据中精确为零。
矩阵近似本身亦有有效最优证书。固定 ,令 的秩至多 。将 维空间 经 映射,其核必非平凡。选取单位向量 使 ,则
在第 个奇异值后截断正好达到此界,故它是最佳秩至多 的谱范数近似。这个定理关于矩阵近似,本身并不决定特定测量问题的不确定性应支持哪个 。
秩揭示是数值任务,并非秩的定义
精确 SVD 以正奇异值揭示精确秩。算出的 SVD 则有舍入误差。若结果由后向关系 支持,正交因子精确且 ,所报奇异值便描述这个邻近矩阵,并有
以下直接证明,而非无解释地诉诸稳定性。奇异值满足
上界可取 的张成空间。下界方面,由维数公式,每个容许的 与 均有非平凡交集;该交集内的单位向量,其像范数至少为 。把 换成 ,每个像范数的变化至多 。双向使用极小极大公式便得到扰动不等式。因此阈值若位于某奇异值的这个误差范围内,便不能建立稳健的秩判定。间隙是否存在、数据不确定性有多大,两者都重要。具体 SVD 实现需要自身经论证的后向误差预算;本节并未实现。
列主元 QR 是另一种实用秩评估方法:每步选取剩余残差范数最大的列,再以正交变换三角化。在精确的秩 分解中可得
令 、,则全部极小者满足 。设 得到基本解。记 、,真正的最小范数成员须最小化
故先解 ,再取 。此系数矩阵正定,因为 时 。这个推导解释了基本解缺少的最小范数步骤,并非建议在要求高的实现中形成这组正规方程。完整正交分解亦可实现相同几何。
浮点算术中,尾部 QR 区块够小、前导区块条件可接受,都是需要量化的证据。只看对角大小的规则并不是 SVD 的秩定义。普通贪心列主元选择是有用启发法,但更强秩揭示界或奇异值估计需要额外分析。本节定义了程序及其精确解几何,并没有证明生产用列主元 QR 程序的普遍秩保证。
算例
例题 15.1.6
(重复列、非零残差及全部极小者)
令
取 、、。奇异值为 ,且 。因此
全部极小者为 ,共同拟合向量为 ,共同残差为 ,范数 。系数范数平方是 ,唯一最小点为 。基本解 的拟合同样好,但范数较大,为 。不可消除的残差与系数不唯一,是不同事实。
例题 15.1.7
(欠定精确拟合仍需选择规则)
对 、,两行线性无关,且
此公式适用于这个满行秩矩阵,并非任意秩下的一般定义。它给出 。每个解均为 ,范数平方为 。因此精确系统虽有无穷多解,最小范数解仍唯一。把第三变量设为零得到 ,范数平方是五而非二。
例题 15.1.8
(阈值以舍弃弱方向换取较小系数)
取 、。精确秩为二。最小范数最小二乘解是 ,残差范数 。第二数据改变 ,相应系数便改变 。
用 时只保留第一个奇异方向,故 、。对原数据的残差为 ,范数为 ,而 。系数向量大幅缩小,代价是残差稍增。代价是否可接受,取决于数据不确定性,并非一个没有解释的机器常数。阈值改变模型的秩;原来精确矩阵仍是秩二。
常见错误
反例模式
跨越秩改变时伪逆不连续
对 、,有 ,但 。 在范数下趋向 ,其伪逆却不收敛。取 ,精确最小范数解在秩消失时由 跳至零。稳定计算不能消除原问题的这种敏感性。
即使固定 且 ,直接得到的也只是右端的绝对敏感性界:
按奇异向量展开即可证明,沿 改变时达到等号。相对系数误差还依赖可能为零或很小的 ;忽略此分母不能得到有限普遍相对界。若同时扰动 并容许秩改变,则需更多假设。
常见错误
(三角矩阵的对角不是奇异值表)
三角矩阵的对角也不是奇异值表。对 ,两个对角元素均为一,但 ,且 ,所以 。此例警告不能把任意未选主元的对角当作 SVD 检查,并非声称反驳每一个有量化假设的列主元 QR 定理。
常见错误
(把自由变量设为零并不给出最短解)
消元或三角求解若把自由坐标设为零,返回的是基本解。它是最小二乘解,但一般不是最小范数解。在重复列的例子中,基本解 的范数为 ,而 的范数为 。检验方法是与零空间正交: 与零空间向量 的内积为 ,所以它不是最短成员。
概念视角结构
秩、可分辨程度及系数度量的选择
精确秩计算固定数据的非零奇异方向。数值秩记录指定不确定性及阈值能分辨哪些方向。最小欧氏(Euclidean)范数选取指定坐标内最短的系数;缩放未知量会改变这个度量,也可能改变选出的解。这是三个明确的建模决定,并非同一个自动答案的三种名称。
小结
SVD 分开可达拟合与不可消除的残差,也分开被决定的系数方向与零空间。伪逆选出唯一位于行空间内的最小范数解。截断具有精确近似及受限拟合意义,但需要明确的分辨决定。精确秩、算出的秩估计及稳定实现相互相关,却各有不同假设。
练习
快速检查
(令 、。求 、全部最小二乘解、最小范数成员及最优残差,并验证正规正交条件。)
解答 · 答案
写 ,则 ,其中 ,所以 。故 ,全部极小者为 。拟合向量为 ,得 ,范数 。直接相乘得 ,而 证明它在仿射解族内范数最小。
快速检查
(令 、,基本解为 。用 QR 讨论中的 推导最小范数解。再以 作 ,改为最小化 ,证明选出的物理向量 改变了。)
解答 · 答案
此处 、、,故 。方程 给出 ,另一坐标亦为 。更改度量后,;其最短精确系数向量为 ,故 。两个物理向量均满足 ,但最小化不同范数。第二规则最小化 ,而非 。
快速检查
(对 、 及严格规则 ,分别求 、、、 时的 、残差范数及矩阵近似误差。)
解答 · 答案
或 时,保留两个正方向:,残差范数一,近似误差零。 时等于阈值者被舍弃:,残差范数 ,近似误差 。 时不保留任何方向:,残差范数 ,近似误差三。每种情况的原矩阵精确秩仍为二。
快速检查
(某算出的 SVD 已有谱范数后向误差预算 ,报告奇异值 、、。取阈值 ,只据此信息可认证原矩阵哪些秩主张?解释阈值秩二实际描述什么。)
解答 · 答案
原第二奇异值位于 ,第三位于 。两个区间都跨过阈值,所以原矩阵的阈值秩可以是一、二或三。第一奇异值必高于阈值;这组特定区间亦保证三个值均为正,所以原矩阵精确秩为三。报告的阈值秩二描述算出因子代表的邻近矩阵在指定严格截断下的结果;误差区间与阈值重叠时,它不能认证原矩阵有相同截断决定。