Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval

Abstract

We present the optimal design of a spectral method widely used to initialize nonconvex optimization algorithms for solving phase retrieval and other signal recovery problems. Our work leverages recent results that provide an exact characterization of the performance of the spectral method in the high-dimensional limit. This characterization allows us to map the task of optimal design to a constrained optimization problem in a weighted $L^2$ function space. The latter has a closed-form solution. Interestingly, under a mild technical condition, our results show that there exists a fixed design that is uniformly optimal over all sampling ratios. Numerical simulations demonstrate the performance improvement brought by the proposed optimal design over existing constructions in the literature. In a recent work, Mondelli and Montanari have shown the existence of a weak reconstruction threshold below which the spectral method cannot provide useful estimates. Our results serve to complement that work by deriving the fundamental limit of the spectral method beyond the aforementioned threshold.

References in corpus (6)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Limit theorems for sample eigenvalues in a generalized spiked population model
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Phase Recovery, MaxCut and Complex Semidefinite Programming
• Sparse Phase Retrieval: Convex Algorithms and Limitations
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization

Cited by in corpus (22)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-invasive focusing and imaging in scattering media with a fluorescence-based transmission matrix
• Phase Retrieval: From Computational Imaging to Machine Learning
• The Numerics of Phase Retrieval
• Large-scale phase retrieval
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
• Reliable Linearized Phase Retrieval for Near-Field Antenna Measurements with Truncated Measurement Surfaces
• Phase retrieval in high dimensions: Statistical and computational phase transitions
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Accelerating ptychographic reconstructions using spectral initializations
• Sparse Signal Recovery from Phaseless Measurements via Hard Thresholding Pursuit
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Unrolled Wirtinger Flow with Deep Decoding Priors for Phaseless Imaging
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Structured Random Model for Fast and Robust Phase Retrieval
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Local saddle structure in relaxed averaged alternating reflections Algorithms on phase retrieval
• Construction of optimal spectral methods in phase retrieval