论文页面 - 稀疏的代价：稀疏与稀疏化测量下稀疏恢复的充分条件

来源：https://huggingface.co/papers/2509.01809

摘要

针对稀疏二进制信号，在高信噪比区域下，本文确定了最大似然支撑集恢复的充分样本量，揭示了信息论阈值以及测量稀疏性与计算成本之间的权衡，分析亦涵盖了稀疏化的稠密设计。

我们考虑从含噪线性测量中恢复稀疏二进制信号的支撑集问题。对于稀疏高斯测量矩阵，我们确定了在高信噪比区域（其中 p 表示信号维度，s 表示信号中非零分量的数量，d 表示测量矩阵每行的期望非零分量数）进行最大似然恢复的最小样本量的充分条件。结合已知的下界，这得出了阶为 (s \log(p/s) / \log(ds/p)) 的信息论阈值，明确了测量稀疏性的代价。特别地，我们强调了这样一个区域：由测量稀疏性引起的样本复杂度损失是对数级的，而计算增益几乎是线性的。其次，我们研究了对原本稠密的高斯设计进行稀疏化后的恢复问题：观测由稠密设计生成，而估计使用独立稀疏化的设计和重新缩放的响应。在比例区域 (s=\alpha p)，(d=\psi p) 中，我们证明，对于每个固定的目标误差水平 (\delta) 和每个松弛量 (\varepsilon>0)，样本量阶为 (p/\psi^2) 即足以在任意小的 (\psi) 下实现支撑集恢复。

查看arXiv页面 (https://arxiv.org/abs/2509.01809) 查看PDF (https://arxiv.org/pdf/2509.01809) 添加到收藏 (https://huggingface.co/login?next=%2Fpapers%2F2509.01809)

在您的代理中获取此论文：

hf papers read 2509\.01809

没有最新的CLI？curl \-LsSf https://hf\.co/cli/install\.sh \| bash

引用此论文的模型 0

没有模型链接到此论文

在模型的README.md中引用 arxiv.org/abs/2509.01809 以从此页面链接它。

引用此论文的数据集 0

没有数据集链接到此论文

在数据集的README.md中引用 arxiv.org/abs/2509.01809 以从此页面链接它。

引用此论文的空间 0

没有空间链接到此论文

在空间的README.md中引用 arxiv.org/abs/2509.01809 以从此页面链接它。

包含此论文的收藏 0

没有收藏包含此论文

将此论文添加到收藏 (https://huggingface.co/new-collection) 以从此页面链接它。