动机
传感器很少给出精确的线性测量。若坚持精确拟合带噪声的观测,拟合出的系数可能解释的是测量误差,而不是背后的信号。另一方面,若允许任意大的偏差,零向量便成为一个容易却毫无信息的答案。我们需要一个容许量:大到足以包含真实信号,又小到足以保留信息。
精确恢复有两个相互独立的障碍。第一,观测可能与 不同。第二,近似稀疏的信号可能有许多小系数,而不是恰好 个非零项。本节推导一个对每个障碍各有一项的误差界。其假设不仅控制零空间中不可见的改变,也控制测量矩阵几乎看不见的改变。常数取决于该矩阵;结论是确定性的,不需要噪声的概率模型。
定义
以下在实数上按精确运算处理。设 ,;对 ,令 在 上等于 ,其余坐标为零,补集记作 。
定义 16.6.1
(最佳 项尾误差与带噪基追踪)
对信号 ,定义
设 ,,其中 是指定的上界。带噪基追踪选取下列问题的任意一个全局最小解:
包含 个绝对值最大坐标的集合达到最小值:若保留了一个较小坐标而舍弃了一个较大坐标,交换二者不会增加被舍弃的和;绝对值相同时可任选。这个最佳集合供分析使用,重建过程不需要预先知道它。若两个坐标绝对值相同而只能保留其一,两种选择都达到同一尾误差;证明只需固定其中一个,而下面的假设对所有允许的集合成立,所以这种并列不影响结论。真实 未知时,这个集合及尾误差也未知:定理描述重建质量与信号可压缩程度的关系,并不是仅凭数据便可计算的误差证书。
为什么使用两种不同的范数?在系数空间, 范数是各坐标绝对值之和,既度量总误差,也使最小化偏向较简洁的表示。在数据空间, 范数把测量残差视为一个向量的欧几里得(Euclid)长度。两者作用于不同空间,不能等同;稳健性质中的常数 正是连接两种尺度的一部分。改变测量单位或重新缩放 ,可用的 也会改变。
真实的 是可行的。因此可行集与半径为 的闭 球相交;在有限维中这个交集是紧致集,连续目标函数在其上达到最小值。球外的点不可能比可行点 更好,所以全局最小解存在。它不一定唯一;下面的结论对每个最小解都成立。
定义 16.6.2
(稳健零空间性质)
若存在常数 、,使每个 及每个 的集合都满足
则称 具有 阶 稳健零空间性质。
这是关于所有向量及所有允许支撑集的假设,并非每个矩阵都具备。对 ,它化为定量的普通零空间不等式;对一般的 ,额外一项度量该改变有多“可见”。只知道定性的零空间结论,并不能提供噪声计算所需的上述常数;只检查少数支撑集或少数试验向量,也不能确立这个对全部向量成立的不等式。
概念视角几何
精确恢复即零空间避开一个锥
对精确数据,极小点就是最小的 球(一个正轴体)与仿射集 相接触的点。因此 是唯一极小点,恰好当没有非零 满足 :零空间与 范数在 处的下降锥只交于原点。 的零空间不等式对每个非零的零空间向量给出 ,因此对每个支撑在 内的 都有 :关于 的一个条件,同时排除了所有 稀疏点的锥。
定理:分开尾项与噪声
定理 16.6.3
(有界噪声下的稳定恢复)
设上述稳健零空间性质成立。令 、,并令 为以该容许量求解的带噪基追踪的任意全局最小解。则
第一项是用 稀疏向量逼近 的代价,第二项是容许测量误差的代价;两者量纲不同、来源也不同。若 是 稀疏的,第一项消失;若数据精确且 ,第二项消失。两者同时消失时,误差界变成精确恢复的结论。
推论 16.6.4
(精确数据下稀疏信号的精确且唯一恢复)
在 阶稳健零空间性质下,若 至多有 个非零项、 且 ,则 是带噪基追踪的唯一最小解。
证明
(误差界的两项同时为零)
此时 且 ,定理对每个最小解 给出 。由上面的紧致性论证,最小解存在,所以最小解的集合恰为 。唯一性在这里是结论,定理并没有假设它。
由于 ,同一右边也控制欧氏(Euclidean)误差,但一般不是在更强假设下可得的更精细的欧氏估计。带较小或不同尺度 项的定理需要另外证明。
证明:一个锥与一个测量界
证明
(锥不等式、测量界与稳健性质)
令 ,并令 包含 中绝对值最大的 个坐标。由于 可行而 使目标最小,
分别在 与 上使用反三角不等式:在 上得 ;在补集上得 。与最优性合并并消去 ,得到锥不等式
系数二并非随意的放宽:移项之前,尾项在两边各出现一次。这个不等式说明,除非原信号有可观的尾项,最小解不能把远多于大坐标上的误差放到大坐标以外。
与 都可行,所以
两个残差可以方向相反,这解释了系数二。它们不必相等:一般 。
依次使用稳健性质、锥不等式及测量界,
由于 ,相除得
锥不等式还给出 。代入并化简即得所示的界:
证明透视
每个假设在哪里用到
证明有三个输入,各用一次。 相对于可行竞争者 的最优性给出锥不等式;这是唯一用到目标函数的地方,也是尾项 出现的原因:反三角不等式的两边各贡献一次。 与 两者的可行性给出 ;这是唯一用到噪声水平的地方。稳健性质是桥梁:它作用在实际误差 上,而 一般不在 中,所以其 项恰好吸收测量界。
收尾一步虽是代数,却不可缺少。稳健不等式用 自身的 倍加上已知项来界定它,只有 才允许把该项移到左边。若 ,不等式与任意大的 并不矛盾,下面的边界反例正说明了这一点。
常见错误
(把只控制零空间的不等式用于带噪数据)
当 ,两个可行向量之差 通常满足 。只控制 的零空间不等式对这个 没有任何结论,所以不能代替稳健性质;没有常数 、 的定性零空间结论也不能。
例题
例题 16.6.5
(已知矩阵、尾项与带噪数据)
取 、、、、。噪声为 ,所以所给容许量有效。对每个 及单元素集合 ,;因此 、 是有效常数。
任何可行 都满足 ,所以 。点 可行且达到这个下界;等号也迫使 及 ,所以这个最小解唯一。最佳一项尾误差为 ,实际误差为 。定理给出 。正确的上界对特定信号与观测不必是紧的。
例题 16.6.6
(真正欠定的矩阵)
令
其零空间是 ,所以有无穷多个向量给出相同测量。尽管如此,它以 、 具有稳健性质。为了对每个 验证,令 。对 ,先用三角不等式,再用 Cauchy–Schwarz 不等式,得
对 ,把 与 互换。对 ,
空集的情形是平凡的,所以所给常数对所有大小至多为一的集合都成立。我们并没有声称 是最优的。对 及精确数据 ,定理表明即使 有非平凡零空间, 仍是唯一最小解。
例题 16.6.7
(边界情形:数据精确,被舍弃的尾项仍改变答案)
保留上面的 ,取 ,,,。每个可行向量的形式为 ,目标值为 ,在三个转折点 的中位数 处取最小。因此唯一最小解是 ,且
尽管观测精确,结果并不精确,因为原向量不是一稀疏的。定理中的尾项允许这种情形;它没有声称此处达到系数六。
例题 16.6.8
(容许残差会收缩解)
仍用同一 ,取 、无噪声数据 ,但容许 。可行性推出 ,所以
向量 可行且达到此界。事实上它是唯一最小解:等号迫使第一个拟合坐标为 且 ;残差球再迫使第二个拟合坐标为零,故 。其误差为 ,而尾项为零,所以保证值是 。即使实际噪声恰好为零,保守的容许量也可能带来重建误差。
假设不成立时
反例模式
零空间边界上的等号并不足够
对 、、、 及 , 与 都是全局最小解:任何可行 都有 。零空间向量 在 内外质量相等,而 。因此无论 取何值,任何 都不满足稳健性质。只允许 既不支持精确恢复,也不允许证明中的除法。
常见错误
(声明的噪声上界小于实际噪声)
令 、、,却错误地声明 。唯一可行点是 。虽然单位矩阵满足稳健性质,而 是一稀疏的,所谓零误差的结论却是错的:实际噪声为 ,所以 不可行。定理没有失效,失效的是其前提。估计或界定噪声是另一项建模工作。
常见错误
(把容许量当作 LASSO 惩罚参数)
带噪基追踪施加的是残差约束;带惩罚的 LASSO 则最小化残差损失与 惩罚之和。在额外条件及适当选择参数下,两者的解可以联系起来,但 并不自动就是 LASSO 惩罚参数,上面的定理也不是关于 LASSO 的定理。
同样,数值求解器若只给出近似可行或近似最优的点,所用的界必须包含这些容许误差;不应把精确最优性默默归于有限步计算。验证稳健性质本身可能很困难。一个有利的例子不能为任意字典作证明,没有更多假设也推不出任何概率、随机设计或限制等距性的保证。
练习
快速检查
(对欠定例题中的矩阵,设 、。计算定理给出的 误差数值上界。这能证明支撑集被精确恢复吗?)
解答 · 答案
这里 、,所以尾项与噪声的系数分别是 与 。上界为 ,约为 。仅有误差界不能证明支撑集精确恢复:任意小的非零系数仍可能被引入或抹去,需要额外的阈值及系数大小假设。
快速检查
(对同一矩阵及精确观测 ,已知真实向量是一稀疏的,求 时带噪基追踪的最小解。无须列出所有可行向量,解释它为什么唯一。)
解答 · 答案
一稀疏向量 给出指定的测量。它的最佳一项尾误差与容许量都是零,所以定理迫使每个最小解都等于这个向量。由上面的紧子水平集论证,最小解存在,所以即使可行集还包含其他非稀疏向量,它仍是唯一最小解。
快速检查
(令 、、、。指出实际噪声,求解约束问题,并准确说明为什么不能套用恢复定理。)
解答 · 答案
实际噪声为 ,其范数 。约束 使 成为唯一最小解。真实信号不可行,所以与 的最优性比较及 测量界都不能使用。
练习 16.6.9
(设定理的假设成立,但计算得到的可行向量 只满足 ,其中 已知。证明下面的界,并说明它对计算残差有什么要求。)
综合证明
解答(4)
- 1
带目标值超额重做锥不等式
令 ,并选取最佳集合 。同样的反三角计算现在给出 。
- 2
保留测量界
。
依据: 与 都满足 。
- 3
使用稳健性质并解出支撑集上的质量
关键一步
依据: 允许把 一项移到左边。
- 4
合并并读出残差要求
∎由 ,代入后得到系数 、 及 。此保证要求 ;若计算残差较大,就须修订测量界。
相关笔记
精确数据的零空间性质解释无噪声基追踪的唯一性判据;LASSO 的近端梯度法讨论另一种带惩罚的目标及可计算的优化证书。