证明了稀疏二值向量可精确恢复，且样本复杂度最优。
Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements
- 采用线性估计方法，结合信息论下界分析。
- 在1比特量化和逻辑回归中，样本复杂度为O((k+σ²)log n)。
- 揭示了1比特压缩感知与逻辑回归无统计-计算鸿沟。
本文研究从广义线性测量中精确恢复k-稀疏二值向量的问题（如逻辑回归）。分析了线性估计算法（Plan, Vershynin, Yudovina, 2017），并推导出测量数的信息论下界。对于带噪声的1比特量化线性测量（1bCSbinary），得到样本复杂度为O((k+σ²)log n)，其中σ²为噪声方差，该结果因信息论下界而被证明最优。同时，也获得了逻辑回归的紧致样本复杂度刻画。由于1bCSbinary比噪声线性测量（SparseLinearReg）更难（因量化引入），因此在SparseLinearReg中也能达到相同样本复杂度。尽管此复杂度可通过Lasso实现，但线性估计更具计算效率。我们的下界适用于任意测量集（此前仅知高斯矩阵情形），并与最大似然上界紧密匹配。对于SparseLinearReg，Gamarnik与Zadik（2017）曾猜想存在统计-计算鸿沟，要求测量数至少为(2k+σ²)log n才能有高效算法。但本工作表明，1bCSbinary与逻辑回归中不存在此类鸿沟。
原文摘要 · Abstract (English)
We consider the problem of exact recovery of a $k$-sparse binary vector from generalized linear measurements (such as logistic regression). We analyze the linear estimation algorithm (Plan, Vershynin, Yudovina, 2017), and also show information theoretic lower bounds on the number of required measurements. As a consequence of our results, for noisy one bit quantized linear measurements ($\mathsf{1bCSbinary}$), we obtain a sample complexity of $O((k+σ^2)\log{n})$, where $σ^2$ is the noise variance. This is shown to be optimal due to the information theoretic lower bound. We also obtain tight sample complexity characterization for logistic regression. Since $\mathsf{1bCSbinary}$ is a strictly harder problem than noisy linear measurements ($\mathsf{SparseLinearReg}$) because of added quantization, the same sample complexity is achievable for $\mathsf{SparseLinearReg}$. While this sample complexity can be obtained via the popular lasso algorithm, linear estimation is computationally more efficient. Our lower bound holds for any set of measurements for $\mathsf{SparseLinearReg}$, (similar bound was known for Gaussian measurement matrices) and is closely matched by the maximum-likelihood upper bound. For $\mathsf{SparseLinearReg}$, it was conjectured in Gamarnik and Zadik, 2017 that there is a statistical-computational gap and the number of measurements should be at least $(2k+σ^2)\log{n}$ for efficient algorithms to exist. It is worth noting that our results imply that there is no such statistical-computational gap for $\mathsf{1bCSbinary}$ and logistic regression.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。