论文标题
带有生成先验的1位压缩感测和二元稳定嵌入的样品复杂性边界
Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors
论文作者
论文摘要
标准1位压缩感测的目的是从二进制值测量值中准确恢复未知的稀疏矢量，每个测量值表明向量的线性函数符号。通过生成模型的压缩感测的最新进展，在这种模型中，生成建模的假设取代了通常的稀疏性假设，我们研究了使用生成模型的1位压缩感应的问题。我们首先考虑无噪声的1位测量值，并提供样品复杂性界限，以在i.i.d.〜高斯测量和Lipschitz连续生成的先验以及近乎匹配的算法与无关的下限下进行近似恢复。此外，我们证明了二进制$ε$稳定的嵌入属性，它表征了重建对测量误差和噪声的鲁棒性，也可以通过Lipschitz连续生成模型具有足够多的高斯测量值来进行1位压缩感。此外，我们将结果应用于神经网络生成模型，并提供了概念验证的数值实验，证明了基于稀疏性方法的显着改善。
The goal of standard 1-bit compressive sensing is to accurately recover an unknown sparse vector from binary-valued measurements, each indicating the sign of a linear function of the vector. Motivated by recent advances in compressive sensing with generative models, where a generative modeling assumption replaces the usual sparsity assumption, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.~Gaussian measurements and a Lipschitz continuous generative prior, as well as a near-matching algorithm-independent lower bound. Moreover, we demonstrate that the Binary $ε$-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models with sufficiently many Gaussian measurements. In addition, we apply our results to neural network generative models, and provide a proof-of-concept numerical experiment demonstrating significant improvements over sparsity-based approaches.
