arXiv:2509.01809 · LLM 基础设施
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
稀疏性的代价：使用稀疏及稀疏化测量的稀疏恢复充分条件
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
- 类型：arxiv
- 标识：2509.01809
- 链接：https://arxiv.org/abs/2509.01809
- 主分类：llm-infra
- 形态：method
- TLDR：We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/p to infty, where p denotes the signal dimension, s the number of non-zero components of the signal, and d the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order slog(p/s) / log(ds/p), making explicit the price of measurement sparsity.
- 待LLM分类：否
- 标题中文：稀疏性的代价：使用稀疏及稀疏化测量的稀疏恢复充分条件
- TLDR中文：我们研究从含噪线性测量中恢复稀疏二值信号支撑集的问题。对于稀疏高斯测量矩阵，我们识别了在高 SNR 范围 ds/p → ∞ 下最大似然恢复所需最小样本量的充分条件，其中 p 表示信号维度，s 为信号非零分量数，d 为测量矩阵每行非零分量期望数。结合已知下界，这给出量级为 s·log(p/s)/log(ds/p) 的信息论阈值，明确揭示了测量稀疏性的代价。
- 成熟度：research
- 场景：稀疏恢复、压缩感知、理论分析
- 来源文件：
- /inbox/tom/_candidates/2026-09-11-agent-rag-longcontext-candidates.json