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
• 被引：0
• 被引来源：Semantic Scholar
• S2被引：0
• 影响力被引：0
• TLDR：It is proved that, for every fixed target error level $\delta$ and every slack $\varepsilon>0$, a sample size of order $p/\psi^2$ is sufficient for support recovery for arbitrarily small $\psi$.
• 待LLM分类：否
• 标题中文：稀疏性的代价：使用稀疏及稀疏化测量的稀疏恢复充分条件
• TLDR中文：证明：对于任意固定的目标误差水平 $\delta$ 与任意松弛量 $\varepsilon>0$，数量级为 $p/\psi^2$ 的样本量足以在任意小的 $\psi$ 下完成支撑恢复。
• 成熟度：research
• 场景：稀疏恢复、压缩感知、理论分析
• 来源文件：
• /inbox/tom/_candidates/2026-09-11-agent-rag-longcontext-candidates.json
• [S2 enrich]