The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik
stat.ML, cs.IT, cs.LG, math.ST
2025-09-02
MIT给出高SNR下稀疏高斯测量做支撑恢复的充分条件，信息论阈值约s log(p/s)/log(ds/p)；后验把稠密设计稀疏化时，样本量要到Θ(p/ψ²)才够。
稀疏恢复问的是：从带噪线性观测Y=Xβ+Z里，找回s-稀疏信号β的非零位置。稠密高斯设计已经有清楚的相变：样本量低于nINF≈2s log(p/s)/log s，信息论上恢复不了；过了这个阈值，最大似然估计（MLE）能找回支撑，但通常要指数时间；再大到nALG≈2s log(p−s)，Lasso才能多项式时间成功。
实际系统更想用稀疏测量矩阵，每行大约只有d个非零，存得少、乘得快。Wang等人给出过必要性下界，充分条件一直缺。Chaabouni和Gamarnik（MIT）补上高信噪比区间的充分条件，把「稀疏要多采多少样本」写成一个因子。第二问更贴近已经拿到稠密数据的人：把设计矩阵事后稀疏化，还能不能恢复。
信号限定为二进制β∈{0,1}^p，找回支撑就等于找回信号。这是压缩感知和稀疏回归里的常用简化，对应非零幅度至少为1的情形。
稀疏测量：X的每个元素是Bernoulli(d/p)掩码乘标准高斯，d是每行期望非零数。观测Y=Xβ+Z，噪声方差σ²固定。SNR定义为ds/(pσ²)。他们盯的是高SNR，即ds/p→∞。估计器是组合MLE：在所有s-稀疏的0-1向量里找残差平方和最小的那个。
证明路线是大偏差加并集界。先用Chernoff界控制「某个错误支撑的MSE比真支撑还小」的概率，关键步骤是在给定稀疏掩码条件下，测量行仍是高斯，从而把行矩母函数写死；再对所有汉明误差至少δ的支撑做并集。得到的充分样本量在s=o(p)时是
nSP = 2s log(p/s) / [log(ds/p) + log(δ/(2σ²))]。
线性稀疏s=αp时，分子换成2h(α)p，h是二元熵。
主动稀疏化是另一套模型。观测仍由稠密高斯X生成，估计却用独立掩码后的X̃和按d/p缩放的Ỹ。Ỹ并不是「稀疏X̃对β的投影」，所以行矩母函数跟着掩码走，朴素Chernoff参数会在指数稀有的坏掩码上退化。他们改用缩小的Chernoff参数θ{p,λ}=λθ（λ∈(0,1)）把退化去掉，代价是ψ必须足够小，以及样本界多一个(1+ε)松弛。这个技巧来自和Claude Opus 4.7的讨论，作者声明所有命题已人工核验。
没有数值模拟，数字都是阈值公式。把充分条件和Wang等人的必要条件下界拼在一起，高SNR稀疏测量出现与稠密情形同类的信息论相变，位置在nINF^SP = 2s log(p/s)/log(ds/p)（s=o(p)）或2h(α)p/log d（s=αp）。
| 设置 | 信息论阈值 | 相对稠密的代价 |
| 稠密高斯 | 2s log(p/s)/log s | 1 |
| 稀疏测量（高SNR） | 2s log(p/s)/log(ds/p) | Γ=log s / log(ds/p) |
| 主动稀疏化（ψ→0） | Θ(p/ψ²) | Θ(log p / ψ²) |
Γ可以是略大于1，也可以任意大，取决于d和s相对p怎么走。例如s=p^α、d=p^β且α+β>1，则Γ=α/(α+β−1)：β靠近1时稀疏几乎免费，β靠近1−α时样本代价爆炸。
一个对从业者更直观的例子：线性稀疏s=αp时，把稠密矩阵换成每行只有缓慢增长的d个非零，样本量从Θ(p/log p)涨到Θ(p/log d)，比值最多是log级；矩阵-向量乘从Θ(p²/log p)降到Θ(pd/log d)，计算增益接近线性。
主动稀疏化侧，对每个固定误差δ和松弛ε，只要保留率ψ足够小，n≥(1+ε)nSP就足以让分数汉明误差掉到δ以下，nSP = 2h(α)p / log(1 + δψ²/[(1−ψ)(2−δ(1−ψ))])。ψ→0时就是Θ(p/ψ²)。反过来，已经有n=Ω(p)条样本时，每行大约可以只留Θ(√(p/n))比例的非零，样本翻倍，稀疏化预算大约乘√2。
Lasso在稀疏测量上的多项式时间保证，仍停在Omidiran–Wainwright的慢稀疏假设（线性稀疏时大约要d=ω(p^{2/3})）。这篇的信息论结果弱到d=ω(1)，中间那截算法阈值仍是空的。
做sketch、压缩感知或高维回归时，如果测量矩阵可以自己设计，这篇给出「稀疏换样本」的兑换率：多付Γ倍样本，换近线性的存算。已经拿到稠密特征、想事后把矩阵打稀来加快估计的人，能用的预算大约是√(p/n)，再稀就超出这篇的充分条件。
这是渐进改进加一块理论拼图，不是新算法。MLE本身是指数时间，不能当实现去跑。和网络剪枝（Optimal Brain Damage那条线）只是类比：那里稀疏化的是权重，这里稀疏化的是设计矩阵。
作者写明：必要性说的是一致精确恢复，充分性只保证MLE的分数汉明误差趋于0，比稠密情形的all-or-nothing弱一档。高SNR（ds/p→∞）是硬假设，更稀的测量没有充分条件。主动稀疏化没有匹配的必要性下界，作者猜想d=o(p)的亚线性保留率下，无论多少样本都恢复不了。ψ必须足够小，是正则化Chernoff的技术代价，不是「ψ大反而更难」的物理结论。没有实验。二进制信号和组合MLE都限制了可迁移性。