在学习理论和高维统计中，稀疏恢复问题一直是研究的热点之一。本文探讨了具有 $\ell_\infty$ 误差保证的稀疏恢复的统计与计算特性。此问题的变体源于变量选择任务，目标是估计在 $\mathbb{R}^d$ 中一个 $k$-稀疏信号的支持。
我们的主要贡献是证明了 $\ell_\infty$ 稀疏恢复的盲目模型（"for each"）与自适应模型（"for all"）之间的可证分离。我们展示，在盲目模型下，最优的 $\ell_\infty$ 误差可在近线性时间内以 $\approx k \log d$ 采样达到，而在自适应模型中，任何算法都需要 $\geq k^2$ 采样才能实现这一界限。
这与标准的 $\ell_2$ 设置形成了显著对比，后者即使在自适应稀疏恢复中也仅需 $\approx k \log d$ 采样。最后，我们初步考察了一种部分自适应模型，表明在 $\approx k \log d$ 测量下，非平凡的变量选择保证是可能的。
博主点评： 本文通过实证分析揭示了盲目模型和自适应模型在稀疏恢复中的根本区别，提供了新的视角来理解变量选择问题的复杂性，尤其是在高维数据处理中的应用意义。