本节讨论:在给定的矩阵扰动下,哪些关于秩的信息得以保留;这与上一单元残差与敏感度的分析是不同的问题。全程使用实有限矩阵()与谱范数。
精确整数也可能对扰动敏感
设 的奇异值为 ,其中 。其精确秩 是严格为正的奇异值数目。这个叙述针对一个精确矩阵。测量值或存储的近似矩阵 可以十分接近 ,却不具有相同的精确秩: 的秩为一,而 对每个 都有秩二,无论 多小。
前一篇低秩近似章节证明,当 ,使秩降至低于 所需的最小谱范数扰动大小为 。事实上,小于 的扰动不可能产生秩至多为 的矩阵;扰动 恰好达到该距离。在另一个方向上,若 ,则对每个 ,扰动 都使秩增加一;新的奇异值可能需要重新排序。若 ,任选单位向量 和 ,则每个 的 都有秩一。因此只要秩未达最大值,它便可能因任意小扰动而上升。若 ,秩不可能再上升,而且谱范数小于 的扰动会保持秩 。
阈值是一项明确决定
定义 6.2.1
(阈值秩)
对选定的容差 ,定义阈值秩 。严格大于的约定明确处理边界。它不必等于精确秩:不大于 的正奇异值被刻意视为未能分辨。容差应反映问题的测量及计算误差尺度;没有这些背景,不能宣称某个数值普遍正确。把数据矩阵乘以标量 ,会使所有奇异值乘以 ,因此绝对阈值带有单位。
定理 6.2.2
(奇异值的稳定性)
假设精确矩阵 具有相同大小,且满足 。奇异值的稳定性不等式是
证明
(极大极小公式与三角不等式)
为完整起见,证明使用变分刻画
使用完整奇异值分解,其右奇异基底为 ;当 ,。前 个右奇异向量的张成空间使最小值至少为 。由维数计数,每个 维空间 都与 的张成空间有非零交集;该交集中某个单位向量满足 。这证明了变分刻画。对每个单位向量 ,三角不等式给出 。对每个 先取最小值,再对 取最大值,得到 ;交换 即证(1)。
证明透视
维数计数与三角不等式在哪里起作用
选用极大极小公式,是因为它不借助奇异向量来描述 ,于是 与 可以在同一批子空间 上比较。关键一步是 对所有单位向量 一致成立(来自 ),而先取最小值再取最大值会保持这种一致不等式。维数计数只用来证明该公式: 维的 与 张成的 维空间,维数之和为 ,所以必有非零的公共向量。最后交换 与 ,把单边不等式变成带绝对值的不等式。这里只假设两矩阵大小相同且 ,对秩本身没有任何假设;因此每个 至多移动 ,精确秩却仍可跳变。
推论 6.2.3
(由不确定区间得出的秩界)
设 如稳定性定理所设,并设 为任意容差,则
证明
(在阈值两侧计数指标)
若 ,则由(1) 得 ,所以指标 被 计入;不同指标仍然不同,这给出左边的不等式。若 ,则 ,所以 被右边计入,这给出右边的不等式。
下界数出肯定高于阈值的奇异值;上界包含每个可能高于阈值的奇异值。即使 ,两界仍然成立。处于不确定区间的值,其分类未必能确定。这里把 视为精确值;若算法输出其近似值,使用此推理前还须把有证明的计算误差纳入不确定度。
例题
例题 6.2.4
(精确秩改变,阈值秩却稳定)
设 、。比较它们的精确秩,并用 及 估计 。
解答。 有两个正奇异值,秩为二; 有三个,秩为三。差 是 ,谱范数为 。对 ,恰有两个奇异值大于 ,也恰有两个大于 。(2) 的上下界都是二,所以 。此例的精确秩不同,阈值结论却是稳定的。
例题 6.2.5
(不确定区间可能使结论无法确定)
已知矩阵 ;未知真实矩阵满足 。这对 有什么启示?
解答。 有一个奇异值大于 ,两个大于 ,故(2) 给出 。两种情况确实都会出现: 和 与 的距离均为 。按严格阈值规则,它们在容差 下的秩分别为一及二。没有更多信息便不能消除不确定性;把任一答案报成确定都会超出数据所支持的范围。
例题 6.2.6
(失去秩的距离与严格阈值)
令 ,则 、,精确秩为二。扰动 满足 ,而 的秩为一:秩可以在距离 处下降。对任何 的 ,不等式(1) 给出 ,所以秩仍为二。在容差 下,奇异值 并不严格大于 ,故 ,尽管精确秩是二。这个边界情形说明,严格不等号是必须明确声明的约定。
反例模式
相近的矩阵未必有相同的精确秩
断言:若 很小,则 。这是假的。取 、,则 的谱范数为 ,但 、。能保留下来的是(2) 的两个界:取 、,只有 大于 ,也只有它大于 (因为 ),所以 被确定下来。容差大于不确定度时答案稳定,精确秩则不然。
常见错误与细节
常见错误
(把测量矩阵的秩当作真实矩阵的秩)
第二个例题中 有 ,但在所述距离内的矩阵 有 。只对测量矩阵使用阈值,就忽略了不确定区间;诚实的答案是(2) 给出的区间。
常见错误
(忘记阈值带有单位)
把数据矩阵乘以 ,所有奇异值都乘以 。取 ,矩阵 的阈值秩为一,而 的阈值秩为二。容差必须按数据的单位和误差尺度来选取。
习题
快速检查
(对 ,求精确秩及阈值秩 。)
先数严格为正的奇异值,再数大于 的奇异值。
解答 · 答案
奇异值为 ,所以精确秩为二。只有 大于 ,故 。
快速检查
(设 、、。当 时,(2) 对 说明了什么?)
把 的奇异值与 比较。
解答 · 答案
只有 大于 ,而 和 都大于 。因此 。两个值都会出现: 给出一,与 距离为 的 给出二。
快速检查
(若 且 ,稳定性不等式对 给出怎样的范围?)
取 应用(1)。
解答 · 答案
,所以 。特别地 , 至少有三个正奇异值。