从唯一性到可计算的目标
宽矩阵可能在足够稀疏的向量之中唯一确定信号,但逐一搜索所有可能的支撑集需要组合搜索。基追踪以绝对值之和代替非零项的数目。这个替换能否保留答案?关键不只是零空间有没有稀疏向量,更在于每个无法被测量察觉的扰动如何分布其质量。
定义 16.5.1
(限制到指标集与基追踪)
设 ,。对 ,令 在 上等于 ,其余坐标为零; 是补集。对无噪声数据 ,基追踪求解
最小解存在:可行集非空,与半径 的闭 球之交是紧致集。球外每个可行点的目标值都大于 ,所以交集上的最小解也是全局最小解。解不一定唯一。以下均处理实向量与精确运算;此约束问题不同于带正惩罚参数的 lasso。
精确判据
两个可行向量相差 中的一个元素,所以关于基追踪的每个问题,其实都是零空间向量如何分布 质量的问题。
定义 16.5.2
( 阶严格零空间性质)
若对每个非零 和每个 的集合,
则称 具有 阶严格零空间性质。若 ,它真空成立。
定理 16.5.3
(零空间刻画)
以下两项等价:
- 对每个至多有 个非零项的 , 是数据 的唯一基追踪解。
- 具有 阶严格零空间性质。
证明
(用反三角不等式证充分性;用拆分零空间向量证必要性)
假设严格性质成立。令 的支撑集包含于 ,,并设另一可行向量为 。则 。若 ,在 上使用反三角不等式得
所以每个不同的可行向量都有严格更大的目标值,唯一性成立。
反过来,若该性质不成立,便有非零 与 ,使 。取 、。因为 ,故 ,而 。又 ,所以 不是唯一最小解:另一可行向量的目标值或更小,或与它相等。必要性得证。
证明透视
严格性与阶数 $s$ 在哪里起作用
充分性只用到两件事。第一,可行的竞争者与 相差一个零空间向量 。第二, 在 上为零,所以竞争者在 上要付出全部质量 ,而在 上反三角不等式说明它至多节省 。严格不等式把“至多节省”变成对每个 都严格净亏损;若只有非严格不等式,只能得到 ,允许持平。
不明显的一步在必要性。把坏的零空间向量 沿 切成 与 。前者至多有 个非零项,所以是第一项中合法的测试信号;阶数 只在这里用到。后者给出相同的测量,因为两者之差是 。等式 已经造成持平,这就是要求唯一性时第二项不能减弱为 的原因。
此性质排除了支撑集大小至多为 的非零零空间向量:把其支撑集分成两个大小至多为 的集合,对两者分别使用严格不等式便得到矛盾。因此每个 稀疏 都是 的唯一 稀疏解。反向不成立,下面的具体矩阵说明了这一点。
反例模式
稀疏唯一性不蕴涵零空间性质
断言:若没有支撑集大小至多为 的非零零空间向量,则基追踪恢复每个 稀疏向量。取 及
每个非零零空间向量的三个坐标都不为零,所以断言的假设成立。取 ,内外质量都是 ,严格性质不成立。具体地, 与 给出 ,两者的 范数都是 。两者都是最小解:任何可行 满足 ,所以 。因此 不是唯一最小解。正确的条件是定理中的 质量不等式,而不是支撑集大小。
非稀疏信号的尾项误差界
精确稀疏是一种理想化。有用的保证应在信号只是接近稀疏时平稳地退化。
定义 16.5.4
(最佳 项 误差)
对任意 ,
取绝对值最大的 个坐标可得到一个最小集合;绝对值相同时可任意选取。这个集合是分析工具,重建算法不需要事先知道它。
定理 16.5.5
(确定性的逐信号误差界)
假设存在 ,使每个 和每个 均满足 。对任意 和精确数据 的任意基追踪解 ,
证明
(比较最小解与真实信号)
令 ,并选取最佳集合 。由可行性知 ,由最小化知 。分别在 和 使用反三角不等式,得
所以 。代入假设,得 。最后
这是对精确测量的确定性界,既没有假设也没有证明测量噪声下的误差界;有噪声时需要适当的稳健假设及修改可行集。
常见错误
(把精确数据的误差界当作噪声界)
若数据为 且 ,真实的 通常不满足 。上面的证明两次用到 的可行性:得出 ,以及比较 与 。两步都不再成立,所以在放宽约束并把零空间假设加强为稳健版本之前,这个不等式对有噪声的数据没有结论。
例题
例题 16.5.6
(一个不可见方向)
取
对任何非零零空间向量及单元素集合 ,内部质量是 ,外部是 。故 时严格性质成立,量化条件也成立,最佳常数为 :每个一稀疏向量都能唯一恢复。例如 给出 ,它是唯一最小解。
同一数据也有另一稀疏表示 ,其 范数为 而非 。因此基追踪不能恢复这个二稀疏 ,因为可行向量 有更小目标值。一稀疏保证不能自动延伸至二稀疏情形。
概念视角分析
逐个信号的对偶证书
零空间性质对所有 稀疏信号一致成立。凸对偶则为一个固定的、支撑集为 的 提供检验: 是唯一的基追踪最小解,当且仅当 中以 为指标的各列线性无关,并且存在 使
对上面的矩阵和 ,取 得 ,从而证明可以恢复。对 而言,条件 迫使 或 ,这与那里两个解同时达到最小 范数的结论一致。
例题 16.5.7
(接近一稀疏信号的逐信号误差界)
保留同一个 、 与 ,常数为 。令 ,则 ,。每个可行向量是 ,目标值为
绝对偏差之和恰在点 的中位数处取最小,所以唯一最小点是 ,,而真实信号的值为 。因此 ,,故
中间不等式也可核对:取 ,。基追踪没有返回 ,但误差受尾项 控制。
例题 16.5.8
(边界情形:阶数等于环境维数)
令 。此时可取 ,,严格性质要求每个非零 都有 。这不可能,所以 阶严格性质成立当且仅当 ,这迫使 。此时可行集 只有一点 ,恢复是平凡的。另外对每个 都有 ,所以误差界给出 。因此宽矩阵()只可能对某些 的阶数满足该性质。
常见错误与练习详解
常见错误
(最稀疏解不一定是唯一 ℓ1 最小解)
“支撑集最小的可行解必然是唯一 最小解。”定理要求检查每个零空间方向。对上面的矩阵 , 是该方程组唯一的一稀疏解,因此也是唯一最稀疏解,却与较稠密的解 同时达到最小 范数。判据中只有相等并不足够。
快速检查
(对第一个例题的矩阵 , 阶严格零空间性质是否成立?)
用零空间向量 测试一个二元素集合。
解答 · 答案
不成立。对 及 ,,而 。拆分构造给出 与 ,正是同一数据的两个表示 与 ,后者范数更小。
快速检查
(对 ,计算 与 。)
保留绝对值最大的坐标,把其余坐标的绝对值相加。
解答 · 答案
时保留 ,剩下 ,故 。 时保留 与 ,剩下 ,故 。
快速检查
(若逐信号误差界的假设在 、 时成立,关于 可得出什么结论?)
把假设应用于每个单元素集合。
解答 · 答案
当 ,每个 对每个单一指标 都满足 。因此 ,。此时可行集是 ,所以 ,与误差界 一致。