Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors

Abstract

Many problems in statistics and machine learning require the reconstruction of a rank-one signal matrix from noisy data. Enforcing additional prior information on the rank-one component is often key to guaranteeing good recovery performance. One such prior on the low-rank component is sparsity, giving rise to the sparse principal component analysis problem. Unfortunately, there is strong evidence that this problem suffers from a computational-to-statistical gap, which may be fundamental. In this work, we study an alternative prior where the low-rank component is in the range of a trained generative network. We provide a non-asymptotic analysis with optimal sample complexity, up to logarithmic factors, for rank-one matrix recovery under an expansive-Gaussian network prior. Specifically, we establish a favorable global optimization landscape for a nonlinear least squares objective, provided the number of samples is on the order of the dimensionality of the input to the generative model. This result suggests that generative priors have no computational-to-statistical gap for structured rank-one matrix recovery in the finite data, nonasymptotic regime. We present this analysis in the case of both the Wishart and Wigner spiked matrix models.

arXiv commentTo appear at NeurIPS 2020

References in corpus (27)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• SegAN: Adversarial Network with Multi-scale $L_1$ Loss for Medical Image Segmentation
• Sparse PCA: Optimal rates and adaptive estimation
• Compressed Sensing using Generative Models
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Provable Bounds for Learning Some Deep Representations
• On Lazy Training in Differentiable Programming
• Global Optimality of Local Search for Low Rank Matrix Recovery
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
• Amortised MAP Inference for Image Super-resolution
• Compressive Phase Retrieval From Squared Output Measurements Via Semidefinite Programming
• Phase Transitions in Semidefinite Relaxations
• Nonsmooth Analysis and Optimization
• Message-passing algorithms for synchronization problems over compact groups
• Computational Lower Bounds for Sparse PCA
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Sparse PCA via Covariance Thresholding
• Sum-of-Squares Lower Bounds for Sparse PCA
• Why are deep nets reversible: A simple theory, with implications for training
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Exact asymptotics for phase retrieval and compressed sensing with random generative priors
• SUNLayer: Stable denoising with generative networks
• Global Guarantees for Blind Demodulation with Generative Priors

Cited by in corpus (1)

• Constant-Expansion Suffices for Compressed Sensing with Generative Priors