揭示稀疏测量下信号恢复的采样代价，明确稀疏性带来的复杂度增益与损失。
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
- 基于稀疏测量矩阵，推导出稀疏信号恢复的样本量下界条件。
- 发现稀疏性使所需样本量增加约 $\log s / \log(ds/p)$ 倍。
- 证明对稠密矩阵稀疏化后仍可有效恢复，适合低密度测量场景研究者。
研究在噪声投影下恢复稀疏信号支撑集的问题。针对稀疏测量矩阵场景，本文建立了成功恢复所需的样本量充分条件。结合已有必要条件，发现在 $ds/p \to +\infty$ 时，稀疏恢复存在信息论阈值 $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log(p/s)/\log(ds/p)\right)$，其中 $p$ 为信号维度，$s$ 为非零分量数，$d$ 为每行测量矩阵的期望非零数。该表达式明确揭示了稀疏性的代价：每测量仅保留 $d$ 个非零项，使样本量放大 $\log s / \log(ds/p)$ 倍，精确刻画了采样复杂度与测量稀疏性的权衡。此外，研究了将稠密测量矩阵稀疏化对恢复的影响，在 $s = \alpha p$、$d = \psi p$ 且 $\psi$ 较小时，证明样本量 $n^{\text{Sp-ified}}_{\text{INF}} = \Theta(p / \psi^2)$ 足够恢复，前提是满足某一统一可积性猜想（证明仍在进行中）。
原文摘要 · Abstract (English)
We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the regime where $ds/p \rightarrow +\infty$, sparse recovery in the sparse setting exhibits a phase transition at an information-theoretic threshold of $n_{\text{INF}}^{\text{SP}} = Θ\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$, 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. This expression makes the price of sparsity explicit: restricting each measurement to $d$ non-zeros inflates the required sample size by a factor of $\log{s}/\log\left(ds/p\right)$, revealing a precise trade-off between sampling complexity and measurement sparsity. Additionally, we examine the effect of sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of $s = αp$ and $d = ψp$ with $α, ψ\in \left(0,1\right)$ and $ψ$ small that a sample of size $n^{\text{Sp-ified}}_{\text{INF}} = Θ\left(p / ψ^2\right)$ is sufficient for recovery, subject to a certain uniform integrability conjecture, the proof of which is work in progress.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。