Cocola Jorio, Hand Paul, Voroninski Vladislav
Department of Mathematics, Northeastern University, Boston, MA 02115, USA.
Khoury College of Computer Sciences, Northeastern University, Boston, MA 02115, USA.
Entropy (Basel). 2021 Jan 16;23(1):115. doi: 10.3390/e23010115.
We provide a non-asymptotic analysis of the spiked Wishart and Wigner matrix models with a generative neural network prior. Spiked random matrices have the form of a rank-one signal plus noise and have been used as models for high dimensional Principal Component Analysis (PCA), community detection and synchronization over groups. Depending on the prior imposed on the spike, these models can display a statistical-computational gap between the information theoretically optimal reconstruction error that can be achieved with unbounded computational resources and the sub-optimal performances of currently known polynomial time algorithms. These gaps are believed to be fundamental, as in the emblematic case of Sparse PCA. In stark contrast to such cases, we show that there is no statistical-computational gap under a generative network prior, in which the spike lies on the range of a generative neural network. Specifically, we analyze a gradient descent method for minimizing a nonlinear least squares objective over the range of an expansive-Gaussian neural network and show that it can recover in polynomial time an estimate of the underlying spike with a rate-optimal sample complexity and dependence on the noise level.
我们对具有生成神经网络先验的尖峰威沙特矩阵和维格纳矩阵模型进行了非渐近分析。尖峰随机矩阵具有秩一信号加噪声的形式，并已被用作高维主成分分析（PCA）、社区检测和群体同步的模型。根据施加在尖峰上的先验条件，这些模型在理论上可通过无界计算资源实现的信息最优重构误差与当前已知多项式时间算法的次优性能之间可能会显示出统计计算差距。人们认为这些差距是根本性的，就像稀疏PCA的典型案例一样。与此类情况形成鲜明对比的是，我们表明在生成网络先验条件下不存在统计计算差距，在这种先验条件下，尖峰位于生成神经网络的范围内。具体而言，我们分析了一种梯度下降方法，用于在扩展高斯神经网络的范围内最小化非线性最小二乘目标，并表明它可以在多项式时间内以速率最优的样本复杂度和对噪声水平的依赖性恢复基础尖峰的估计值。
