基追踪的稀疏恢复证书

欠定系统保留的全部不确定性在 $\ker A$ 中。同一观测的其他解是 $x+h$，$h\in \ker A$。${\ell }_1$ 解码偏爱总绝对值小的向量，因此真正要排除的是：一个核方向把真支持内的质量削掉，却只在支持外付出更少的质量。

式(2)并没有声称整个 $p$ 维空间等距。它只管短支持向量。证明的关键是把可能很稠密的误差拆成“大块”和若干逐渐变小的尾块：大块若不为零，其测量长度有正下界；尾块的总作用却不够抵消它。两边来自同一个核向量，必须精确抵消，矛盾就迫使误差为零。

图中黑色的真支持、蓝色的第一块和红色的后续块表示同一误差的分解。条形只表示排序关系，不是一条可能同时满足全部恢复条件的非零核向量；绿色结论恰好说明这样的非零误差不可能存在。

完整证明：从最优性到零误差 ​

固定任意至多 $s$ 稀疏的 $x$ 和式(1)的任意最优解 $\hat{x}$。记 $S=\mathrm{supp}(x)$、$h=\hat{x}-x$。若 $x=0$，零向量可行且目标为零，任何最优解都必须为零；以下考虑非空支持。可行性给 $Ah=0$，目标比较给

所以

这是无噪声等式约束的常数一锥；Lasso 基本不等式理路Lasso 基本不等式与预测误差Lasso basic inequality · Lasso prediction error bound从带优化容差的目标比较推导预测界与松弛锥，分清噪声事件、稀疏结构、设计条件和可计算证书各自的作用。的常数三锥来自另一个带噪声、带惩罚的问题，不能混用。

将 $S^c$ 的坐标按 $|h_j|$ 非增排列，按连续的 $L=\lambda s$ 个分为 $S_1,S_2,\dots ,S_r$；最后一块不足时保留其实际大小。令 $T=S\cup S_1$，空块不列入。对每个 $i\ge 2$，前一块一定有 $L$ 个坐标，且当前块每个绝对值不超过前一块的最小值，从而不超过其平均值。因此

逐块求和，注意前一块的总和至多为全部支持外质量，得

若只有一块或根本没有支持外坐标，左端是零，式(6)仍成立；不需要虚构一个满长的最后块。

由于 $Ah=0$，有 $A{h}_T=-\sum _{i\ge 2}A{h}_{S_i}$。$|T|\le s+L=k$，而每个尾块至多 $L\le k$，故式(2)、三角不等式、式(6)、式(5)依次给

倒数第二步用Cauchy–Schwarz理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，且 $|S|\le s$。条件 $\beta /\sqrt{\lambda }<\alpha$ 迫使 $h_T=0$。此时 $h_S=0$，式(5)又迫使 $h_{S^c}=0$，故 $h=0$。证明对任意 $x$ 和任意最优解都成立，所以结论既统一又唯一；严格不等式若变成等号，最后一步就不能这样推出。

七个观测，恢复八个坐标中的任意一个 ​

令 $p=8$。对 $k=1,\dots ,7$，矩阵 $Q$ 的第 $k$ 行前 $k$ 个元素为 $1/\sqrt{k(k+1)}$，第 $k+1$ 个为 $-k/\sqrt{k(k+1)}$，其后为零；定义 $A=\sqrt{8/7}Q\in {\mathbb{R}}^{7\times 8}$。

每行之和为零、长度为一。若 $k<\ell$，第 $\ell$ 行在第 $k$ 行的非零位置上取相同值，所以两行内积等于该相同值乘第 $k$ 行的和，即零。于是 $Q{Q}^{\mathsf{T}}=I_7$，其行空间正是 ${\mathbf{1}}^{\perp }$，从而

列范数全为一，不同列的内积全为 $-1/7$。任意三列的 Gram 都是 $8I_3/7-{\mathbf{1}}_3{\mathbf{1}}_3^{\mathsf{T}}/7$：常数方向的特征值为 $5/7$，与它正交的二维空间上为 $8/7$。因此对全部 $(\genfrac{}{}{0ex}{}{8}{3})=56$ 个支持，统一取

式(2)通过，故所有一稀疏信号都可精确恢复。结论包含任意实幅值和任意支持，并非只验证八个单位向量。单位列只是选择了明确的坐标尺度，没有使用 $A^{\mathsf{T}}A=I_8$ 这种欠定系统不可能满足的条件。

还可从另一个方向核验：$\ker A=\mathrm{span}\{\mathbf{1}\}$，非零核向量在一坐标上的质量是 $|c|$，其余为 $7|c|$。对 $x=e_j$，取 $u=A_j$，则 $A_j^{\mathsf{T}}u=1$，其他相关性全为 $-1/7$，原始目标和对偶目标均为一。$x=-e_j$ 时将 $u$ 也取反。这里的精确核与对偶证书和上面的全支持 Gram 证明相互独立地核对同一端点。

能区分所有一稀疏信号，基追踪仍然会选错 ​

取

任意两列线性无关；任何两个一稀疏向量的差至多二稀疏，所以它们不可能给出相同观测。相应二列 Gram 的最小特征值为 $(11-\sqrt{85})/18>0$，而相对单位尺度的 ${\delta }_2=(7+\sqrt{85})/18<1$。这些性质足以保证稀疏识别，尚未指定一个正确的凸解码器。

实际上 $z=(1/3,1/3,0)$ 也满足 $Cz=y$，却有 $\Vert z{\Vert }_1=2/3<1=\Vert x{\Vert }_1$。全部可行点可写成

$f$ 在 $t<0$、$0<t<1$、$t>1$ 的斜率分别是 $-5/3,1/3,5/3$，所以唯一最小点为 $t=0$。取 $u=(1,1)$，有 $C^{\mathsf{T}}u=(1,1,2/3)$、$y^{\mathsf{T}}u=2/3$，再次精确认证凸最优解是 $z$。优化证书完全正确，信号恢复却失败。

核向量 $(-1,-1,3)$ 在第三坐标上有质量三，另外两坐标只有二，揭示了失败的原因。改变第三列尺度会改变 ${\ell }_1$ 偏好：若第三列改为 $(a,a)$，$a>0$，则 $e_3$ 对应的替代解为 $(a,a,0)$，目标为 $2a$；当 $a<1/2$ 真信号失败，$a=1/2$ 出现一整段最优解，$a>1/2$ 时该真信号成为唯一最优解。列缩放因此也改变了我们对未知坐标大小的先验偏好。

不满足证书，不等于必定失败 ​

对 $p=8$ 的同一单纯形矩阵，如果要求 $s=2,\lambda =2$，则 $k=6$，特征值界为 ${\alpha }^2=2/7,{\beta }^2=8/7$，比值四不小于二，式(2)不能使用。但核向量在任何至多二坐标上的质量至多 $2|c|$，补集至少 $6|c|$，下文的严格核条件仍证明所有二稀疏信号可恢复。充分条件的失败只表示这份证书没有给出保证。

为什么对偶 gap 必须连同可行性报告 ​

对式(1)按拉格朗日对偶理路拉格朗日对偶Lagrange duality通过拉格朗日函数构造原问题下界的对偶问题，并研究弱对偶、强对偶与最优性条件。取 $\mathcal{L}(z,u)=\Vert z{\Vert }_1+u^{\mathsf{T}}(y-Az)$。若 $\Vert A^{\mathsf{T}}u{\Vert }_{\mathrm{\infty }}\le 1$，对 $z$ 的下确界为 $y^{\mathsf{T}}u$；若某个相关性绝对值大于一，沿相应符号放大该坐标，拉格朗日函数趋于负无穷。因此对偶问题是最大化 $y^{\mathsf{T}}u$，约束 $\Vert A^{\mathsf{T}}u{\Vert }_{\mathrm{\infty }}\le 1$。弱对偶已经足够证明式(4)，无需把强对偶当作尚未证明的前提。

对可行点，差值还可逐坐标写成

若候选支持为 $S$，在 $S$ 上的相关性等于 $\mathrm{sign}(z_S)$，支持外严格小于一，并且 $A_S$ 满列秩，则 $z$ 是唯一最优解。理由是任意同目标值最优点都必须让上述非负项全为零；严格的支持外相关性迫使那些坐标为零，剩下的同观测等式与满列秩迫使活动坐标也相同。这是这次支持与符号的唯一性证书，并不自动认证其他稀疏信号。

若 $Az\ne y$，数值 $\Vert z{\Vert }_1-y^{\mathsf{T}}u$ 就不再是原始可行上界与对偶下界之差。最简单的反例是 $A=(1),y=1,z=0,u=0$：两目标数都是零，所谓 gap 也是零，可行残差却为一，真实最优值为一。更一般地，真正非负的代数项为

浮点实现应分别报告 $\Vert Az-y{\Vert }_2$、$max(0,\Vert A^{\mathsf{T}}u{\Vert }_{\mathrm{\infty }}-1)$、原始与对偶目标以及使用的容差。小残差和小数值 gap 是数值近似检查，不能称为已经证明无噪声精确恢复。

核条件给出恰好够用的刻画 ​

所有至多 $s$ 稀疏信号都由式(1)唯一恢复，当且仅当对每个 $0\ne h\in \ker A$ 和每个 $|S|\le s$，

充分性：对支持包含于 $S$ 的 $x$ 及任意非零可行扰动 $h$，三角不等式给 $\Vert x+h{\Vert }_1\ge \Vert x{\Vert }_1-\Vert h_S{\Vert }_1+\Vert h_{S^c}{\Vert }_1>\Vert x{\Vert }_1$。必要性：若某个非零核向量违反严格式(9)，取 $x=-h_S$，则 $x+h=h_{S^c}$ 与它同观测，且目标不大于它；若严格更小则 $x$ 非最优，若相等则 $x$ 无法成为唯一最优。两种情况均否定统一唯一恢复。这通常称为零空间性质；这里它精确刻画同一个解码接口何时统一成功。

十五个观测与线性摘要迁移 ​

把前述构造改为 $p=16,m=15$，同样有 $A^{\mathsf{T}}A=(16I_{16}-\mathbf{1}{\mathbf{1}}^{\mathsf{T}})/15$。任意 $q$ 列 Gram 的谱是 $(16-q)/15$（常数方向）和 $16/15$（其余 $q-1$ 个方向）。取 $s=2,\lambda =2,q=6$，于是 ${\alpha }^2=10/15,{\beta }^2=16/15$，比值仍是 $8/5<2$。对全部二稀疏信号的证明来自这个统一谱公式，枚举 $(\genfrac{}{}{0ex}{}{16}{6})=8008$ 个子矩阵只是独立复算。

例如 $x_3=1,x_{12}=-2$，其余为零。取 $u=Av$，其中 $v=(15/16)(e_3-e_{12})$。因为 ${\mathbf{1}}^{\mathsf{T}}v=0$，有 $A^{\mathsf{T}}u=e_3-e_{12}$；支持外相关性全为零，原始与对偶目标均为三，且活动两列满秩。由此得到精确的一次解码证书，再由六列谱公式得到独立的统一矩阵证书。

同一固定 $A$ 也可接到线性 Sketch理路线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。：坐标更新 $(j,\mathrm{\Delta })$ 时令 $y\leftarrow y+\mathrm{\Delta }{A}_j$，两个站点保存相同矩阵与坐标约定时直接相加。更新与合并依旧线性，基追踪解码不必线性。本构造每次更新最坏影响全部 $m$ 个实数，存储为 $m$ 个实数坐标；矩阵系数一般含平方根。仅仅 $m<p$ 不能推出少量比特、常数更新时间或抗任意精度误差的流算法。显式存矩阵的费用、生成列的费用和数值精度都要另计。

如何独立复算，何时该换问题 ​

标准库复算器只使用 Python 的有理数和组合枚举，无需安装 LP 求解器。它写 $A=DB$：$B$ 的第 $k$ 行为 $k$ 个一和一个 $-k$，$D_{kk}^2=p/((p-1)k(k+1))$。因此 $B$ 与 $D^2$ 可精确存成有理数，$A^{\mathsf{T}}A=B^{\mathsf{T}}{D}^{2}B$ 也可精确复算。输入测量用行缩放后的 $w=D^{-1}y=Bx$ 表示；这没有更换解码的可行集，因为 $D$ 可逆。

解码器只接收 $w$，先解 $B{z}_0=w,{\mathbf{1}}^{\mathsf{T}}{z}_0=0$，再利用全部解为 $z_0+t\mathbf{1}$，以 $-z_{0j}$ 的中位数最小化 $\sum _j|z_{0j}+t|$。偶数 $p$ 时须报告两个中间次序统计量之间的完整最优区间，不能无条件宣布唯一。脚本精确检验 16 个有符号单位输入、15×16 的迁移输入、全部对应 Gram 子矩阵、对偶相关性和失败例，并提供读者自行输入有理测量的命令；它是这个特殊可解析矩阵族的求解器，不是通用 LP 软件。一次构造并缓存增广方阵逆需 $O(p^3)$ 次有理算术和 $O(p^2)$ 个有理数存储；随后每个测量用 $O(p^2)$ 次算术求零均值解，再用 $O(p\log p)$ 次比较排序取中位数。直接构造 Gram 需 $O(p^3)$ 次算术，此结构下枚举所有 $k$ 列谱检查需 $O((\genfrac{}{}{0ex}{}{p}{k})k^2)$ 次算术与比较。这些计数没有把有理数位长作为常数成本保证；大分子分母的比特费用须另计。完整题目、答案和命令见稀疏恢复终点练习。

一般矩阵的式(1)可写成线性规划：最小化 $\sum _j{t}_j$，约束 $-t_j\le z_j\le t_j$、$Az=y$。解这个 LP 与验证矩阵对全部稀疏信号满足式(2)是两项不同的计算；朴素的全支持认证有组合数量的子矩阵，本页的对称结构特意避开了这一困难。若观测含噪声，等式约束可能不可行，或迫使算法拟合噪声；应改写带误差半径的约束或明确的损失惩罚，并重新证明误差界，不能直接沿用本页的 $Ah=0$。受限特征值理路受限特征值与稀疏可识别性Restricted eigenvalue condition · Compatibility condition for Lasso · Lasso 兼容条件在稀疏误差锥上定量比较预测与参数范数，精确定标兼容常数和受限特征值，并处理非零优化容差。和Lasso 优化证书理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。处理的是相邻但不同的接口。