Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation
This work addresses the theoretical understanding of initialization methods for nonconvex optimization in high-dimensional signal processing, offering insights into performance thresholds and computational complexity, though it is incremental as it extends prior analyses from specific problems to broader models.
The paper provides a precise asymptotic characterization of a spectral initialization method for arbitrary generalized linear sensing models in high-dimensional nonconvex estimation, revealing a phase transition where performance shifts from random guesses to signal alignment based on sample-to-dimension ratios, with simulations confirming accurate predictions at moderate dimensions.
We study a spectral initialization method that serves a key role in recent work on estimating signals in nonconvex settings. Previous analysis of this method focuses on the phase retrieval problem and provides only performance bounds. In this paper, we consider arbitrary generalized linear sensing models and present a precise asymptotic characterization of the performance of the method in the high-dimensional limit. Our analysis also reveals a phase transition phenomenon that depends on the ratio between the number of samples and the signal dimension. When the ratio is below a minimum threshold, the estimates given by the spectral method are no better than random guesses drawn from a uniform distribution on the hypersphere, thus carrying no information; above a maximum threshold, the estimates become increasingly aligned with the target signal. The computational complexity of the method, as measured by the spectral gap, is also markedly different in the two phases. Worked examples and numerical results are provided to illustrate and verify the analytical predictions. In particular, simulations show that our asymptotic formulas provide accurate predictions for the actual performance of the spectral method even at moderate signal dimensions.