以下矩阵均为实的有限维矩阵。证明使用本课程前面建立的奇异值分解与正交性结果。
两种衡量近似的方法
假设以秩至多为 的较简单矩阵 取代 。下面两种范数回答不同的问题,虽然同一个截断奇异值分解会同时使它们最小。
定义 4.4.1
(谱范数、弗罗贝尼乌斯(Frobenius)范数与截断奇异值分解)
对 ,谱范数是 ,即所有单位输入中的最大伸长量;弗罗贝尼乌斯(Frobenius)范数是 ,即各矩阵项平方和的平方根。
取完整奇异值分解 ,奇异值依次为 ,其中 , 为相应的标准正交奇异向量。秩 的截断为
空和 是零矩阵。每个加项的秩至多为一,所以 。谱范数只由一个方向控制,弗罗贝尼乌斯范数则把所有被舍弃的方向加起来,所以下面陈述中两个最小误差的形式不同。
定理 4.4.2
(Eckart–Young 最佳低秩近似)
设 与 如上。对每个秩至多为 的 ,
当 ,,两个最小误差均为零。
证明分三部分:计算候选矩阵 的误差,证明谱范数的下界,再证明弗罗贝尼乌斯范数的下界。这些是近似定理;舍弃小奇异值会改变矩阵,也可能改变逆问题。
先计算候选矩阵的误差
引理 4.4.3
(截断矩阵的误差)
对 ,;当 ,。
证明
(奇异向量坐标下候选矩阵的误差)
正交坐标变换保持欧氏长度及弗罗贝尼乌斯范数。对后者,一个直接证明是 ,且对正交 有 ;左乘正交矩阵的证明类似。在奇异向量坐标下, 是矩形对角矩阵,其剩余对角项为 。它的弗罗贝尼乌斯范数平方就是这些数的平方和。对矩形对角矩阵,单位向量的最大伸长量是最大对角项的绝对值:平方相加给出上界,选取对应的坐标向量便取到上界。因此当 ,其谱范数是 。
为什么其他秩至多为 的矩阵不能改善最坏情况
证明
(谱范数下界:用被 消去的向量)
假设 。令 ,其维数为 。 限制在 上的像维数至多为 。秩–零度定理给出非零 满足 ;将它标准化至 。写 ,由标准正交性得 及
谱范数是所有单位输入的最大值,所以至少为 ;候选矩阵恰好达到下界。即使有零奇异值或重复奇异值,此维数论证仍然有效;我们没有假设 可逆。
证明透视
谱范数下界从何而来
论证靠两个事实。第一, 的维数是 ,而 的秩至多为 ,所以 限制在 上不可能是单射;秩条件只在这里用到。第二,在 上 都不小于 ,因为奇异值已按次序排列;次序只在这里用到。不显而易见的一步,是把测试向量取在 内,而不是直接比较 与 :这样未知矩阵 就从 中消失。论证能够收尾,是因为下界 恰好等于 的误差,而 的核含有 。若 只有 维, 在其上可以是单射,就不能保证存在满足 的非零 。
为什么误差平方和也最小
证明
(弗罗贝尼乌斯下界:投影到行空间)
令 为 的行空间, 为到 的正交投影。则 且 。矩阵 与 在弗罗贝尼乌斯内积下正交:其迹乘积含有 。因此
把 扩展为 的标准正交基底 ,并对 设 。令 。正交投影给出 ,而 。在 基底下,
第二个等式成立,因为 时 ,其余 都在零空间;也可以在奇异值分解的基底中取迹。
当 ,利用奇异值的次序,
中间的不等式使用 。整理(3)得 。当 ,,同一个下界立即成立。结合(2)即证得(1)的弗罗贝尼乌斯不等式。证明没有假设最佳矩阵与 具有相同的奇异向量;它适用于每个符合秩条件的 。
反例模式
保留范数最大的列不是最佳秩一近似
有人以为秩一近似只需保留范数最大的列、把其余列换成零。取 。则 的特征多项式为 ,所以 ,。由(1),每个秩一的 都满足 及 。第二列 的范数较大;保留它得 ,秩为一,而 ,两种误差都等于 。这个捷径并不最佳;截断奇异值分解用的是奇异方向 ,不是 的坐标列。
例题
例题 4.4.4
(分清两种误差)
设 。求一个最佳秩一近似及其两种范数误差;再对秩至多为二的情况重做。
所列对角项就是按递减次序排列的奇异值。最佳秩一近似之一为 。误差是 ,所以 ,而 。对秩至多为二,,两种误差均为 。定理证明这些值在所有指定秩的矩阵中最小,而不只是对角候选矩阵中最小。
例题 4.4.5
(重复奇异值与不唯一性)
对 ,给出两个不同的最佳秩一近似并计算误差。
取 及 ,两者秩均为一。其误差的对角项分别是 及 ;两者的谱范数均为 ,弗罗贝尼乌斯范数均为 。公式(1)证明两者在两种范数下都是最佳近似。首两个奇异值相同,允许保留不同的奇异方向;不能由“截断奇异值分解”这个名称推断唯一性。
例题 4.4.6
(秩为零与满秩的极端情形)
对 ,取 及 。
当 ,唯一的近似矩阵是 ,误差就是 本身:,,与(1)在 时一致。当 ,截断矩阵 ,两种误差均为零;此时不使用谱范数公式 ,因为没有 。
常见错误
常见错误
(以为两种范数的误差相同)
对 及 ,谱范数误差是 ,弗罗贝尼乌斯范数误差却是 。截断在两种范数下都是最佳,但最佳值是不同的数:谱范数误差只反映被舍弃的最大奇异值,弗罗贝尼乌斯范数误差则反映全部。
即时检查
快速检查
(某矩阵的奇异值为 。它的最佳秩一近似的谱范数误差与弗罗贝尼乌斯范数误差各是多少?)
舍弃 。
解答 · 答案
由(1)取 ,谱范数误差为 ,弗罗贝尼乌斯范数误差为 。
快速检查
(一个 矩阵的秩为 。在 中,哪些 使 的谱范数误差为零?)
哪些奇异值为零?
解答 · 答案
此处 ,,而 。 时谱范数误差为 , 时 。 时误差为 。所以 或 。
快速检查
(对 ,秩为一的矩阵 能否满足 ?)
与 比较。
解答 · 答案
不能。由(1)取 ,每个秩至多为一的 都有 。 与 都达到这个下界。