The goal of compressed sensing is to estimate a vector from an
underdetermined system of noisy linear measurements, by making use of prior
knowledge on the structure of vectors in the relevant domain. For almost all
results in this literature, the structure is represented by sparsity i
本文主要研究了基于生成模型的压缩感知问题，通过下界分析表明基于 L-Lipschitz 生成模型的压缩感知需要线性测量数至少是 k 乘以对数级别的，同时指出生成模型可以作为一种结构表示方法进行推广。作者还构造了一个具有 ReLU 激活的神经网络模型，其层数为 O (1)，每层的激活函数个数为 O (kn)，且该模型可以表示所有 k 稀疏向量。
研究表明，在压缩感知中，如果将稀疏性假设替换为未知向量接近某个合适选择的生成模型的范围，则所需测量的数量可能显著减少。本文使用极小化统计分析工具，建立了与上界对应的算法无关样本复杂性下界。我们证明，除非有进一步的假设，否则 (Bora et al.，2017) 中得出的定律是最优的或接近最优的，其中生成模型是 L-Lipschitz 函数和有界 k 维输入，或者是具有深度 d 和宽度 w 的 k 输入 ReLU 网络。