Constant-Expansion Suffices for Compressed Sensing with Generative Priors
Constant-Expansion Suffices for Compressed Sensing with Generative Priors
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
C. Daskalakis;Dhruv Rohatgi;Manolis Zampetakis
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Dhruv Rohatgi;Manolis Zampetakis
生成神经网络在为压缩感知提供有效的结构先验方面非常有前途，因为它们可以被训练成在高维信号空间中跨越低维数据流形。尽管所得到的优化问题的非凸性，它也已被证明，在理论上，对于具有随机高斯权重的神经网络，在网络的范围内的信号可以有效地，近似地从几个嘈杂的测量恢复。然而，这些理论保证的一个主要瓶颈是网络可扩展性条件：神经网络的每一层必须比前一层大一个对数因子。我们的主要贡献是打破这种强膨胀性假设，表明恒定的膨胀性足以得到有效的恢复算法，除了它也是信息理论上必要的。为了克服现有方法中的理论瓶颈，我们证明了一个新的随机函数，可能不是Lipschitz，但满足一个宽松的概念，我们称之为“伪Lipschitz一致浓度定理。“使用这个定理，我们可以证明，一个称为权重分布条件（WDC）的矩阵浓度不等式，以前只知道它适用于具有对数纵横比的高斯矩阵，实际上也适用于恒定纵横比。由于WDC是一个基本的矩阵浓度不等式，在这个问题上的所有现有理论保证的核心，我们的更严格的约束立即产生在压缩感知与深生成先验的文献中的所有已知结果的改进，包括一位恢复，相位恢复，低秩矩阵恢复，等等。
Generative neural networks have been empirically found very promising in providing effective structural priors for compressed sensing, since they can be trained to span low-dimensional data manifolds in high-dimensional signal spaces. Despite the non-convexity of the resulting optimization problem, it has also been shown theoretically that, for neural networks with random Gaussian weights, a signal in the range of the network can be efficiently, approximately recovered from a few noisy measurements. However, a major bottleneck of these theoretical guarantees is a network expansivity condition: that each layer of the neural network must be larger than the previous by a logarithmic factor. Our main contribution is to break this strong expansivity assumption, showing that constant expansivity suffices to get efficient recovery algorithms, besides it also being information-theoretically necessary. To overcome the theoretical bottleneck in existing approaches we prove a novel uniform concentration theorem for random functions that might not be Lipschitz but satisfy a relaxed notion which we call "pseudo-Lipschitzness." Using this theorem we can show that a matrix concentration inequality known as the Weight Distribution Condition (WDC), which was previously only known to hold for Gaussian matrices with logarithmic aspect ratio, in fact holds for constant aspect ratios too. Since the WDC is a fundamental matrix concentration inequality in the heart of all existing theoretical guarantees on this problem, our tighter bound immediately yields improvements in all known results in the literature on compressed sensing with deep generative priors, including one-bit recovery, phase retrieval, low-rank matrix recovery, and more.