稀疏恢复：给解码结果附上两份证书 ​

形式陈述 ​

完成本页后，你应能交出一个完整结果：从欠定观测算出候选，检查原始可行性与对偶最优性，再用独立的矩阵证书说明哪些真信号确实被恢复。还要能拒绝三种不够用的证据：“全部短列集独立”“一次求解器成功”和“打印的 gap 很小”。

核心接口是基追踪的稀疏恢复证书理路基追踪的稀疏恢复证书Basis pursuit recovery certificate · RIP certificate for sparse recovery · 基追踪与受限等距恢复从无噪声欠定观测建立 ℓ1 解码器，用完整分块证明和可精算的单纯形矩阵分开认证优化最优性与统一稀疏恢复。。若矩阵与范数还不熟悉，先补矩阵理路矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。、向量范数理路赋范向量空间Normed vector space带满足正定、齐次与三角不等式范数的向量空间。和Cauchy–Schwarz理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。。受限特征值理路受限特征值与稀疏可识别性Restricted eigenvalue condition · Compatibility condition for Lasso · Lasso 兼容条件在稀疏误差锥上定量比较预测与参数范数，精确定标兼容常数和受限特征值，并处理非零优化容差。用于辨别稀疏与锥条件；线性摘要理路线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。是末尾的更新与合并迁移，不是开始解码前必须学完的整条路线。

固定 $p\ge 2$，定义 $(p-1)\times p$ 的整数矩阵 $B$：第 $k$ 行前 $k$ 个元素为一，第 $k+1$ 个为 $-k$，其余为零。令正对角矩阵 $D$ 满足

数学观测是 $y=Ax$，精确复算时输入行缩放后的 $w=D^{-1}y=Bx$。不要将 $B$ 的未经缩放 Gram 当作 $A$ 的 Gram。未知信号不作为解码器的输入；答案中的真值只用于出题及事后核对。

直觉 ​

先问算法有没有解对给定目标，再问目标有没有选中真信号。两份证书可能一起成功，也可能第一份成功、第二份失败。反例恰好说明了为什么要保留这两个问题。

这个矩阵族的好处是全部核方向都相同：$z$ 与 $z+t\mathbf{1}$ 有相同观测。解一个欠定凸问题便能化成沿一条直线找中位数。一般矩阵未必有这个捷径，但可行性、对偶相关性、目标值和统一恢复条件仍是可以重复使用的报告接口。

例子与边界 ​

任务一：七个测量值，不先猜支持 ​

取 $p=8$、$w=(1,1,1,1,1,1,1{)}^{\mathsf{T}}$。

1. 解 $B{z}_0=w,\sum _j{z}_{0j}=0$，给出全部可行点。求 $\sum _j|z_{0j}+t|$ 的最优区间，报告 $\hat{x}$
2. 从 $A^{\mathsf{T}}A$ 构造一个可行对偶 $u$，报告相关性向量、原始目标、对偶目标、gap 与精确可行残差
3. 证明 $A$ 的任意三列 Gram 的谱，选 $s=1,\lambda =2$ 核验严格常数差。为什么检查 16 个有符号单位向量还不是统一恢复证明？
4. 把任务的输入改成 $-2w$，不重新运行通用 LP，给出解和对偶证书

任务二：把恢复证明补到最后一个坐标 ​

设 $L=\lambda s$ 为正整数，$S$ 为真支持，$S_1,S_2,\dots$ 按支持外误差绝对值降序，每块大小至多 $L$。

1. 从 ${\ell }_1$ 最优性推出常数一锥，并解释 $Ah=0$ 来自哪个假设
2. 证明 $\sum _{i\ge 2}\Vert h_{S_i}{\Vert }_2\le \Vert h_{S^c}{\Vert }_1/\sqrt{L}$，明确为什么前一块是满块，最后一块为何不构成例外
3. 用受限下界和尾块上界拼出 $\alpha \Vert h_{S\cup S_1}{\Vert }_2\le (\beta /\sqrt{\lambda })\Vert h_{S\cup S_1}{\Vert }_2$，完成 $h=0$ 与唯一性
4. 将严格条件换为等号，或只核验真支持上的最小奇异值，哪一步失去依据？

任务三：十五乘十六的迁移，保留量词 ​

取 $p=16$，观测仍由相同构造得到。本题用于核对的真信号为 $x_3=1,x_{12}=-2$，其余为零。

1. 算 $w$，从 $w$ 求零均值解和中位数，恢复候选
2. 对所有六列子矩阵证明统一谱公式，核验 $s=2,\lambda =2$。写出需枚举的支持个数，但不要以枚举代替证明
3. 用 $u=A[(15/16)(e_3-e_{12})]$ 给出一次优化证书，说明活动两列为什么满秩
4. 对所有至多二稀疏信号，再用核质量给出第二种统一证明。若换回 $p=8,s=2$，上述保守 RIP 条件失效是否意味着恢复失败？

任务四：一个正的稀疏下界，仍会返回错误信号 ​

令

1. 逐对检查列独立性，算非平凡二列 Gram 的特征值，并说明所有一稀疏信号可识别
2. 参数化全部可行点，求基追踪唯一解。给出可行对偶，证明这不是数值求解器的错误
3. 用一个核向量指出严格零空间条件在哪里失败。将第三列改为 $(a,a)$，$a>0$，精确求出该真信号成功、失败和非唯一的分界
4. 对标量问题 $A=(1),y=1,z=0,u=0$，解释为什么打印的目标差零不是合法的原始—对偶 gap

任务五：一次更新、一回合并与一份可重跑报告 ​

1. 两台机器使用相同 $A$。机器甲依次更新 $(3,+1),(12,-1)$，机器乙更新 $(12,-1)$。写出各自状态和合并结果，判断何时可调用二稀疏恢复保证
2. 说明本构造的状态维数、最坏单坐标更新费用和实数精度的额外责任。两个站点分别使用 $D$ 和 $2D$，直接相加是否仍符合协议？
3. 运行下方标准库脚本，核对 56 和 8008 个 Gram，以及包含零信号的 530 次符号/支持解码。解释为什么有理结果比浮点误差显示为零更强，但仍不是一般矩阵的认证算法
4. 在 $p=8$ 中取 $x=(1,1,1,1,0,0,0,0)$。报告中位数最优区间，说明解码器为何必须允许非唯一结果

推论与应用 ​

答案一：从测量解出候选，再看它是否可认证 ​

$B{e}_1=w$，且 $B\mathbf{1}=0$。$B$ 的秩为七：它的行两两正交且非零，或逐行用新的第 $k+1$ 坐标消元。因此全部可行点为 $e_1+c\mathbf{1}$。令其和为零，得到

$-z_0$ 的中间两个次序统计量都为 $1/8$，所以 $t=1/8$ 是唯一中位数，$\hat{x}=e_1$。这个推理从 $w$ 解方程得到候选；没有把“真支持是一”当成算法已知条件。

取 $u=A{e}_1=A_1$，有

因此对偶可行，$P=1,D=y^{\mathsf{T}}{A}_1=1,G=0$，$A\hat{x}-y=0$。支持外相关性严格小于一，支持列长度为一，故该最优解唯一。

任意三列 Gram 为 $(8I_3-{\mathbf{1}}_3{\mathbf{1}}_3^{\mathsf{T}})/7$，常数方向特征值 $5/7$，零和方向特征值 $8/7$。故 ${\alpha }^2=5/7,{\beta }^2=8/7$，$2-{\beta }^2/{\alpha }^2=2/5>0$。分块定理对所有幅值和支持成立。测试 16 个向量只能检查实现错误；任意实幅值上的结论还需齐次性，而支持外竞争解的排除需要定理或核证明。

输入变成 $-2w$ 时，解为 $-2e_1$，可取 $u=-A_1$，相关性取反，仍在无穷范数单位球。此时 $P=D=2$、gap 和可行残差都为零。对偶不必乘二，因为其相关性上限始终是一。

答案二：每一步消耗的条件都写出来 ​

最优性给 $\Vert x+h{\Vert }_1\le \Vert x{\Vert }_1$，而三角不等式给 $\Vert x+h{\Vert }_1\ge \Vert x{\Vert }_1-\Vert h_S{\Vert }_1+\Vert h_{S^c}{\Vert }_1$，相减得常数一锥。$Ah=0$ 则同时使用真信号模型 $y=Ax$ 与候选的精确等式可行性。

若 $S_i$ 存在且 $i\ge 2$，前一块一定含有 $L$ 个元素，否则分块已结束。排序使本块每个绝对值至多为前块平均绝对值，因而

求和时前块索引从一到倒数第二块，质量之和至多为全部支持外质量。只有一块时左端为空和零，所以证明不需要除以一个短块大小。

置 $T=S\cup S_1$，用 $A{h}_T=-\sum _{i\ge 2}A{h}_{S_i}$ 得

严格常数差给 $h_T=0$，随后由锥给 $h_{S^c}=0$。任意最优解都满足这条链，故唯一性成立；零信号的唯一性直接来自零目标。若常数恰为等号，非零长度不会立刻矛盾。若只检查真支持，既没有对 $S\cup S_1$ 的下界，也没有对未知尾块的上界，不能写出这条链。

答案三：新的支持和幅值，共用同一矩阵证明 ​

逐行计算 $Bx$ 得

因为 $\sum _j{x}_j=-1$，零均值解为 $z_0=x+\mathbf{1}/16$。其第三坐标为 $17/16$，第十二坐标为 $-31/16$，其余十四个坐标为 $1/16$。$-z_0$ 的两个中间值都是 $-1/16$，所以解码返回 $x$。

对任意六列，Gram 为 $16I_6/15-{\mathbf{1}}_6{\mathbf{1}}_6^{\mathsf{T}}/15$，谱为 $10/15$ 一次、$16/15$ 五次。共有 $(\genfrac{}{}{0ex}{}{16}{6})=8008$ 个支持，公式与支持身份无关；比值 $8/5<2$ 证明所有二稀疏信号的恢复。

取 $v=(15/16)(e_3-e_{12})$，则 $\sum _j{v}_j=0$，$A^{\mathsf{T}}Av=e_3-e_{12}$。相关性在活动坐标上分别为 $1,-1$，外部为零；$D=x^{\mathsf{T}}{A}^{\mathsf{T}}Av=3=P$。活动 Gram 的特征值为 $14/15,16/15$，所以满秩；严格对偶证书给一次解码的唯一性。

核仍为常数向量，任何二坐标上的质量至多 $2|c|$，补集至少 $14|c|$，严格核条件直接成立。对 $p=8,s=2$，RIP 所用六列比值为四，保守条件失败，但核质量为至多 $2|c|$ 对至少 $6|c|$，仍严格分离。这说明“没通过这份充分证书”与“已经构造出失败输入”是不同结论。

答案四：把失败归到正确的一层 ​

列对 $(1,2),(1,3),(2,3)$ 的行列式依次为 $1,1/3,-1/3$，都不为零。后两对的 Gram 具有特征多项式

所以特征值为 $(11\pm \sqrt{85})/18$。最小值为正；最大的绝对偏离一是 ${\delta }_2=(7+\sqrt{85})/18<1$。两个一稀疏表示若同观测，它们的二稀疏差就在核中，与二列独立矛盾。因此可识别性成立。

全部可行点是 $((1-t)/3,(1-t)/3,t)$，目标在三个区间上的斜率为 $-5/3,1/3,5/3$，唯一最小点在 $t=0$，返回 $(1/3,1/3,0)$。对偶 $u=(1,1)$ 给相关性 $(1,1,2/3)$，$P=D=2/3$、gap 零。凸目标被正确求解；失败在于它比真信号更偏爱两项小系数。

核向量 $h=(-1,-1,3)$ 的第三坐标质量三，大于补集质量二，违反严格零空间条件。将第三列改为 $(a,a)$ 时，可行目标为 $2a|1-t|+|t|$。$t<0$ 斜率 $-(2a+1)$，$0<t<1$ 斜率 $1-2a$，$t>1$ 斜率 $2a+1$。所以 $a<1/2$ 唯一最优为 $t=0$，$a=1/2$ 全部 $t\in [0,1]$ 最优，$a>1/2$ 唯一最优为 $t=1$。这里结论针对指定真信号，并未声称大 $a$ 时所有一稀疏信号都能由基追踪恢复。

标量候选 $z=0$ 不满足 $z=1$。$\Vert z{\Vert }_1-yu=0$ 不是可行原始上界减对偶下界；真正最优值为一。任何数值报告都应把残差和对偶可行性与目标差分开列出。

答案五：可合并性、求解成本和精度分开核算 ​

机器甲的状态为 $A_3-A_{12}$，机器乙为 $-A_{12}$，相加为 $A_3-2A_{12}=Ax$。共享同一矩阵、坐标编码和数值约定时，精确加法保持观测；合并频率向量确实至多二稀疏，故可调用 $p=16,s=2$ 的统一恢复定理。若两段各自稀疏、合并后支持却超过二，不能直接沿用同一稀疏保证。

状态有十五个实数，单次坐标更新最坏改变十五项。矩阵若显式存储需 $15\cdot 16$ 个系数；本构造可由列号按公式生成，仍需计入生成与运算时间。精确实数坐标不是十五个有限比特；实际数值误差需要另外分析。若第二个站点用 $2D$，合并状态为 $DB{x}_A+2DB{x}_B$，一般不等于 $DB(x_A+x_B)$，违反协议。

下载Python 标准库复算器，可直接运行：

python3 basis-pursuit-recovery-reader.py
python3 -O basis-pursuit-recovery-reader.py
python3 basis-pursuit-recovery-reader.py --p 8 --measurement 1,1,1,1,1,1,1
python3 basis-pursuit-recovery-reader.py --p 16 --measurement 0,-2,1,1,1,1,1,1,1,1,23,-1,-1,-1,-1

前两条应给相同的 JSON。自检中，八列矩阵测试零信号及 16 个带符号单位输入；十六列矩阵测试零信号、32 个带符号单点输入和 $(\genfrac{}{}{0ex}{}{16}{2})\cdot 4=480$ 个带符号双点输入，共 $17+513=530$ 次。每次解码函数只收到 $w$，然后独立核对真值、精确残差、对偶相关性、gap 和严格支持余量。Gram 部分由有理权重直接重算，并逐个检查常数特征方向和零和特征方向，数目分别为 56 与 8008。

脚本构造一次增广方阵的逆需要 $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)$ 次算术与比较。它没有隐藏一个通用 LP 求解过程。这些是算术操作次数；有理分子分母的位长会影响每次操作的真实成本，不是单位成本的任意精度比特界。

半支持例的零均值解为 $(1/2,1/2,1/2,1/2,-1/2,-1/2,-1/2,-1/2)$，最优平移区间为 $[-1/2,1/2]$，目标恒为四。两端分别为 $(0,0,0,0,-1,-1,-1,-1)$ 与原来的 $x$，所以非唯一。核在四坐标与补集上的质量相等，恰好解释这个边界。脚本如实返回区间，不把任选一个中位数当成唯一性证明。

参考资料 ​

完整的可达性、受限奇异值分块证明、对偶推导和严格核条件见基追踪的稀疏恢复证书理路基追踪的稀疏恢复证书Basis pursuit recovery certificate · RIP certificate for sparse recovery · 基追踪与受限等距恢复从无噪声欠定观测建立 ℓ1 解码器，用完整分块证明和可精算的单纯形矩阵分开认证优化最优性与统一稀疏恢复。。该页使用 Vershynin 第一版 2024-05-20 作者文件 §10.5.2 的确定性定理，以及 Candès–Tao 的 arXiv:math/0502327v1 第 5–6 页区分稀疏识别与凸解码；本页所有具体矩阵、答案与标准库计算均独立展开。