动机
贪婪近似每次选一个有希望的字典元素,相关计算往往比搜索全部子集便宜。但高相关可能来自错误原子模仿多个真实元素的组合。要证明选择确实识别稀疏表示,必须限制错误原子模仿完整真实支撑的能力。
前面的追踪笔记已推导残差更新,并区分普通匹配追踪与正交重拟合。本节补完整恢复证明。主要设定是有限、确定且无噪声。两两原子相关界会导出小子集线性无关、稀疏系数唯一,以及每一步选择正确;这是三个不同结论,各自需要论证。
充分相干门槛不是必要条件,不符合门槛也不表示每个信号都失败。另一方面,稀疏表示唯一不保证贪婪法在指定步数找到它。最后,样本字典向量也未必稳定表示连续函数;样本恢复与节点间近似仍是不同问题。
定义
定义 16.1.1
(归一字典的相干度)
设有限实字典 ,每列向量满足 。其相干度为 ;只有一列,即 时,定义 。支撑是不同列指标的集合,至多有 个非零系数称为 稀疏。以 表示主要定理的真支撑;它恰有正整数 个元素,每个对应系数非零。
对已选指标集合 ,令 为 中相应各列组成的子矩阵,以最小二乘最小化 。若这些列线性无关,系数唯一,残差为 ,其中 投影到已选列的张成空间;残差与全部已选原子垂直。此处“独立”是确定向量的线性无关,不是观测的概率独立。
定义 16.1.2
(正交匹配追踪)
正交匹配追踪(orthogonal matching pursuit,OMP)从 及 开始。只要残差非零,就在未选指标中选一个使 最大者,加入 ,用最小二乘重新拟合全部已选系数,再重新计算残差。采用固定的相等处理规则,例如取最小指标,算法便完全确定。残差为零或达到指定预算时停止。定理使用精确算术及至少为 的预算。
重拟合不可省略。普通追踪只增加一个原子的倍数,未必重新与旧原子正交。本节归纳依赖每步正交投影。原子归一也属设定;若不归一,相关大小还混入任意列长,不能使用同一选择分析。
定理 / 命题
定理 16.1.3
(相干度控制独立性及稀疏唯一性)
任意含 个原子的子集满足
若 ,该子集线性无关。特别地,若 ,每个信号最多有一个至多 稀疏的系数表示。
唯一性说明贪婪方法应当找到什么;第二个定理则说明 OMP 何时确实找到它。
定理 16.1.4
(完整无噪声 OMP 恢复保证)
设 恰有 个非零系数,且
OMP 只选 中的指标,并在 次选择后精确恢复全部系数;残差不会更早变为零。真原子之间的相等不影响保证,因为证明给出最大真相关与每个假相关之间的严格间隙。
证明思路
证明
(Gram 界、独立性与稀疏唯一性)
对第一个定理,把 展开为对角项与交叉项。对角项之和为 ;交叉项的绝对贡献至多为 。恒等式 ,连同 ,把该和限制在 以内。这证明了两个 Gram 不等式;下因子为正时,也证明了线性无关。
两个至多 稀疏表示若生成同一向量,其差只涉及至多 列。严格相干条件使这些列独立,故差为零,证明唯一。但这还没有证明贪婪法能找到该表示。
证明
(对正确 OMP 选择作归纳)
归纳假设已选的是真支撑的真子集。正交残差仍在全部真原子张成空间,故可写为 ,表示因独立性而唯一。残差不能零,否则原信号可由真支撑的真子集表示,与全部真系数非零矛盾。
选残差表示中绝对值最大的系数。对应真原子相关至少为 ,任何假原子相关最多为 。前者严格较大,恰好就是定理的条件。已选原子的相关因重拟合为零,所以大的真相关必定属未选真原子,下一步选择正确。
完成真稀疏数目的选择后,集合就是全真支撑,最小二乘拟合等于信号,唯一系数等于原系数。证明在精确无噪声模型下不限制真系数大小,但不因此给任意有界噪声相同支撑保证。
证明透视
每个假设在归纳中的位置
三件事用在三个不同地方。张成空间不变量,即先前每次选择都正确,使残差保持 的形式;只有这样才能使用相干比较,而第二个例题说明一次选错便破坏它。严格条件 只用一次,用来分开真原子的下界 与假原子的上界 ;正因为间隙是严格的,真原子之间相等并无害处。正交重拟合使已选原子的相关为零,所以胜出的真相关属于新原子。真原子列的线性无关使 唯一,并排除在第 步之前出现零残差。这些都不能用“残差范数下降”这一观察代替。
若已知正确支撑,而数据改为 ,其中 ,重拟合给出的系数误差至多为 。事实上,系数变化是对 的最小二乘响应,而第一个定理给出最小奇异值的下界。重建信号的误差至多为 ,因为它是 的正交投影。这些是已知支撑下的条件界,并没有证明有噪声的 OMP 会找到该支撑。
相干条件的严格性不是技术细节,边界上的一个具体配置说明了这一点。
反例模式
在相干边界上,相等可能选中假原子
断言:在边界 上保证仍然成立。取 及单位向量
则 ,,所以 ,。令 ,。三个相关为 、、。按最小指标规则,OMP 选中假原子 。残差为 ,它与 、 的相关都是 ,故其次选第二个原子。两个已选原子都在前两个坐标的平面内,而 的第三坐标是 ,所以 次选择后残差 仍非零。第三步会选 ,重拟合后 的系数为零,但“恰好 次、只选真原子”的恢复已经失败。修正后的陈述就是原定理,带严格不等式 。
例题详解
例题 16.1.5
(符合保证的非正交恢复轨迹)
取 、、 及 。相干度为 ,所以定理覆盖二稀疏信号。令 。初始相关为 、、 及 ,所以第一次选第四个原子。
第一次系数为 ,残差为 ,新相关为 ,因此第二次选第一个。重新拟合后,第一及第四原子系数为一及二,残差零。第四个原子的系数会改变;若冻结第一次数值,就不是这里的 OMP。
例题 16.1.6
(表示唯一,OMP 仍可先选错)
三维字典取前两坐标及 。三列线性无关,信号 在整个字典中表示唯一,但与假第三原子的初始相关是 ,比两个真相关都大,所以先选错。
首残差为 。用最小指标相等规则,再选第一个。正交重拟合系数为第一个二分之一、第三个 ,残差为 ,两步后仍非零。相干门槛不成立,单靠表示唯一无法修补错误首选。
例题 16.1.7
(有噪声时须换一种识别结论)
对第一个例题的支撑,Gram 特征值为 及 。若此支撑已知而噪声范数至多为 ,系数误差至多为 ,重建信号误差至多为 。这些估计把系数的条件性与信号精度分开。
即使正交字典也无法在任意有界噪声下识别任意小的非零系数。真信号 加噪声 ,与无噪声信号 的观测相同。正系数不超过噪声容许量时,两种解释都合法。系数下界是排除此消去的必要信息,但单独不足,还须有噪声选择分析保证选对;另一做法是改用不要求精确支撑的成功准则。
稠密字典每次相关扫描需 。每步重建 QR,全部选择的拟合成本为 ;逐步维持正交基则可降至 ,加上扫描共 ,额外因子存储 。这是算术成本,不表示所有有限精度实现同样稳定。
常见错误
常见错误
(把相干门槛当作必要条件)
相干界是充分而非必要,违反它的字典仍可恢复很多特定信号。等号边界没有严格比较,因此本定理不保证,上面的边界配置正是如此。数值上的近似相等不能当作证明中的严格间隙,有噪声实现亦需停止容许值,不能盲目等待精确零。
常见错误
(对在全部节点为零的样本函数归一)
连续字典函数取样时,先形成加权样本向量,再对非零范数归一。相干度描述的是这个取样几何;函数若在全部节点为零,根本不能变成归一原子。连续线性无关不会防止不良节点丢失信息。
常见错误
(把样本正交性当作连续精度)
若有限函数空间有下范数比较 ,正数 才能把空间内样本差控制成连续误差:除以其平方根即可。相干度本身不提供这个比较;第四道练习的相干度为零,误差仍然放大。目标不在空间时,还有连续近似残差及其样本混叠,必须另外处理。
总结
有限归一字典有清楚相干分析。小子集条件先给稀疏唯一性,严格相关比较再证每步无噪声 OMP 恢复,正交重拟合提供归纳不变量。噪声、有限精度及由样本移到连续函数,都需要精确恢复定理以外的信息。
练习
快速检查
(字典相干度为 ,列数足够。严格定理覆盖的最大整数稀疏数是多少?任意三列子字典的奇异值平方有何界?)
解答 · 答案
条件为 ,所以 ,覆盖的最大整数为二。对三列,奇异值平方介于 与 之间。稀疏度为三时恰为等号,所以严格定理不适用。
快速检查
(用第一个例题的字典及最小指标相等规则,追踪信号 的两步选择、重拟合系数及残差。)
解答 · 答案
初始相关一、一、零及 ,先选第一个,系数一、残差第二原子。未选相关为一、零及 ,故再选第二个。两个正交原子重拟合系数皆一,残差零。
快速检查
(说明噪声可消去真系数时的识别障碍,为何相干零不能排除?给一种有噪声精确支撑保证所需的额外信息。)
解答 · 答案
加上噪声 的观测,与无噪声的 的观测相同。若 在噪声容许量之内,仅凭该观测,任何程序都无法区分这两种解释。正交性使无噪声的方向互不相同,却不能揭示被消去的信号。非零系数相对于噪声的大小下界,是排除这种消去的必要条件,但单独并不足够;还须有适当的有噪声选择分析,合并的假设才能给出恢复保证。
快速检查
(在正负 两点取样常数及输入函数,每个节点的概率权重明确为 ,其中 。求归一样本相干。若两响应分别被扰动负及正 ,求负一至一均匀概率测度下的连续平方积分范数误差。)
解答 · 答案
每节点权重为 时,归一样本原子是 及 ,任何正 都相干零。响应扰动对应拟合函数 ,其连续范数是 ,样本范数则为 。节点向原点合并时,即使样本完全正交,连续误差仍可放大。