Title: Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation,
Abstract: 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.