动机
稀疏模型用字典中少量列向量表示信号。上一节证明了正交匹配追踪(OMP)在无噪声下的恢复保证。实际测量很少完全准确,因此现在必须分清两个问题:假如有人告诉我们哪些列向量真正起作用,噪声会使拟合系数偏离多少?假如支撑集未知,观测得到的相关值何时足以辨认它?
第一个问题用已知支撑集上的普通最小二乘回答;第二个问题使用单步阈值选取。以下结果都是确定性的:噪声可以是对抗性的,我们不假设任何概率分布。这不是含噪声 OMP 正确选取支撑集的定理。一种方法的充分条件,不能未经证明就搬用到另一种方法上。
定义
令 的列向量均为单位向量,并沿用上一节,以 为其相干度;当 时规定 。对大小为 的索引集 , 由相应列向量组成, 称为 Gram 矩阵。除非另有下标,以下向量范数均为欧氏(Euclidean)范数。
定义 16.2.1
(含噪声稀疏模型及其参数)
观测值为 ,其中 恰为非零系数的索引集、,且 。其参数为
由于每个原子均为单位向量,Cauchy–Schwarz 不等式给出 。这些参数是未知信号的性质或界,并非假设算法都知道。辨认支撑集时假设 ,且数目 已知。
定义 16.2.2
(单步相关阈值选取)
给定 及稀疏度 ,单步相关阈值选取选出 最大的 个索引 ;取值并列时可任意取舍。此方法在选取前不更新残差,也不重拟合。
定理与命题
定理 16.2.3
(Gram 界与已知支撑集拟合)
对每个大小为 的非空 , 的每个特征值 均满足
若 ,则 的列向量线性无关,且在给定支撑集上的最小二乘估计唯一,满足
更精确地说,重建信号的误差是 ,其中 是到 的正交投影;观测残差则是 。
概念视角代数
用圆盘定理读出 Gram 界
特征值区间也可以直接从 的元素读出。该矩阵是实对称矩阵,每个对角元为 ,每个非对角元的绝对值不超过 。Gershgorin 圆盘定理把每个特征值放在某个以对角元为圆心的圆盘内,半径是该行非对角元绝对值之和:
对称性使 为实数,于是圆盘收缩为定理中的区间。中间的量从不比相干度界差;若选中的原子中只有少数几对接近平行,它会更小。
第二个结果处理未知的支撑集。它只比较相关值,Gram 界要到最后才回来控制重拟合。
定理 16.2.4
(单步阈值选取的充分分离条件)
在同一模型下,若
则每个真实原子与 的绝对相关值均严格大于每个错误原子的绝对相关值。因此选出绝对相关值最大的 个索引便恢复 ;真实索引之间的并列如何取舍都不影响结论。此裕量本身推出 ;因此在选出的支撑集上重拟合便得到上述两个误差界。
证明
证明
(二次型界与投影恒等式)
对 ,展开二次型并利用相干度定义可得
最后一步使用 Cauchy–Schwarz 不等式 。将所得二次型上下界用于特征向量,即得特征值界。若下界为正, 迫使满足 的 为零。故 列满秩,正规方程有上述唯一解。
令 。最小二乘正规方程说明 ,所以 ;正交投影给出 。结合 ,便得到系数误差界。另一方面,用 减去拟合值得到的是另一个向量 。
阈值选取的证明直到最后一行才用到特征值;它是两族内积的比较。
证明
(比较最弱的真实相关值与最强的错误相关值)
对真实索引 ,反三角不等式及 给出
对错误索引 ,三角不等式给出
由于 且 ,假设中的裕量推出 ,故 。假设中的严格不等式还使第一个界严格大于第二个界,因此前 个位置不可能包含错误索引,必然恰好选中全部 个真实索引。这是对所有索引同时成立的比较,允许负系数及对抗性噪声;证明不要求真实相关值保持无噪声时的符号。
证明透视
每个假设在比较中的作用
单位范数用了两次。在 中,自身系数的因子是 ,而每个交叉项都以 为界。单位范数还给出 。
关键一步是不逐一追踪符号。一个下界对所有真实索引成立,一个上界对所有错误索引成立,所以一个数就把两组分开。无论真实相关值之间如何排序,前 个索引组成的集合都已确定。
常数 计算干扰的数目:真实原子遇到其余 个真实原子,错误原子则遇到全部 个。噪声在两边各出现一次,因而得到 。
论证分两步收尾。严格不等式排除两组之间的并列,已知 则使算法恰好在选完真实原子时停止。若 未知,仅靠分离并不给出算法:要在两个界之间确定截断值,就需要未知的信号参数。最后, 把裕量转化为 ,所以第一个定理无需额外假设便适用于重拟合。
此裕量是充分条件,并非必要条件。它使用最大系数 ,仿佛所有干扰相关值同时达到最坏符号与大小,因此即使阈值选取成功,条件也可能不成立。若没有 的界,用 代替可得到较弱但仍正确的条件。这个替换依赖列向量已归一化,下面的验算说明这一点。
反例模式
列向量未归一化时噪声界失效
断言:对正交但未归一化的列向量,用原始内积计算 ,条件 仍保证阈值选取正确。取 中的 、、 及 。不同列向量的原始内积均为零,故 ,且 。
观测值为 ,它与三个列向量的原始相关值是 、 及 。取 时,阈值选取必然选中索引 以及索引 之一,因此失败。
出错的一步是 :这里 超过 ,因为 。修正方法是把字典归一化,用 代替 。相关值变为 、 及 ,严格裕量 保证恢复 。
例题
例题 16.2.5
(先选取,再重拟合)
令 、、,取 、 和 。则 、、 及 。条件成立,因为
相关值分别为 、 及 。前两者最大,因此阈值选取恢复 。在选出的标准正交列向量上重拟合得到 ;系数误差与信号误差的范数都是 。一般相干度界为 ;它成立但偏保守,因为实际选中列向量的 Gram 矩阵是单位矩阵。残差为零:位于选中子空间的噪声被拟合系数吸收。
例题 16.2.6
(唯一不代表条件良好)
取 、,其中 。两列线性无关,故其张成空间内每个向量的表示均唯一。其 Gram 特征值是 。特别地,系数向量 的范数为一,但 。当 ,距离为一的两个系数向量可以产生任意接近的信号。每个固定正角度都有唯一解,但角度缩小时反问题的稳定常数无界增大。
例题 16.2.7
(唯一表示未必能由阈值选取恢复)
令 、、,并令 。三列线性无关,因此即使允许使用整个字典,表示仍唯一。但它们与 的绝对相关值为 、、。取 时,单步阈值选取的是索引 ,而非真实支撑集 。此例不满足充分裕量;唯一性并不保证其结论。
常见错误
常见错误
(稳定的拟合不能证明支撑集正确)
正的 Gram 下界保证给定支撑集上的拟合稳定,并不告诉我们给定的支撑集是否正确。选取支撑集需要系数相对噪声的裕量,而任何条件性界都不提供这一点。同样地,最小二乘残差为零不代表观测没有噪声,“先选取,再重拟合”一例就说明了这一点。 是线性无关的充分条件,并非必要条件;它不成立并不证明矩阵奇异。
常见错误
(把系数误差当作噪声的一部分)
噪声有正交分解 ,故 。系数误差 属于 ,不在信号空间内;只有经 映射后,它才成为上述分量之一。其范数可以大于 ,但倍数至多为 。
常见错误
(接受裕量取等号)
两个估计相等时不能排除真实索引与错误索引并列。在标准正交字典中取 、 及 。则 、 且 ,恰好 。观测 的相关值是 与 ,并列取舍规则可能选出错误索引 。
如果噪声抵消一个非零系数,即使字典标准正交,也不能仅凭观测辨认该支撑集。最后,这里对有限取样向量的分析,本身既不控制取样点之间的误差,也不证明含噪声 OMP 的逐步选择正确。
总结
相干度控制选定 Gram 矩阵的所有特征值;当下界为正时,它也控制已知支撑集拟合中的噪声放大。另一方面,逐一比较真实及错误相关值,可在明确的严格裕量下证明单步阈值选取恢复支撑集。两种估计均为充分界,并非所有成功字典或信号的完整刻画。
习题
快速检查
(归一化字典的 。估计任意四列子字典的奇异值平方与 2-范数条件数。若真实支撑集有四列且 ,求已知支撑集系数误差的上界。)
解答 · 答案
Gram 特征值等于奇异值平方,位于 。因此任意这样的子字典均为单射,其 2-范数条件数不超过 。系数误差不超过 ,约为 。
快速检查
(在三列标准正交字典中,取 、 及 。观测到什么?任何确定性规则能否仅凭观测向量,区分此解释与另一个具有相同噪声限额的二稀疏解释?)
解答 · 答案
观测向量为 ;支撑集 、系数 及噪声 也产生同一观测。两个解释的稀疏度均为二,噪声范数均为 。确定性规则在两个模型中看到完全相同的数据,只能给出相同输出,故即使已知 ,也不能对两者都正确。此处 、 且 ,所以所需的严格裕量不成立。这种抵消现象说明为什么一致保证需要噪声与信号的分离。
快速检查
(在“先选取,再重拟合”一例的字典中,取 、 及 。计算所有相关值、已知 时选出的支撑集、重拟合系数及残差。使用精确的 时,充分阈值条件是否成立?)
解答 · 答案
相关值是 、 及 。最后一个小于一,故阈值选取 。重拟合系数为 ,残差为 。此处 ,充分条件成为 ,确实成立。
快速检查
(令 。证明可能更精细的条件 也保证单步阈值选取正确。解释它为何至少与定理中的条件一样宽松。)
解答
对真实索引,。每个错误相关值至多是 。题设使前一个界严格大于后一个界,故恢复成功。由于一个系数的大小为 ,其余 个至多为 ,所以 。因此
原条件使右边为正,因此推出新条件;新条件也可能在原条件不成立的情况下成立。