In phase retrieval we want to recover an unknown signal @math from @math quadratic measurements of the form @math where @math are known sensing vectors and @math is measurement noise. We ask the following weak recovery question: what is the minimum number of measurements @math needed to produce an estimator @math that is positively correlated with the signal @math ? We consider the case of Gaussian vectors @math . We prove that - in the high-dimensional limit - a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For @math no estimator can do significantly better than random and achieve a strictly positive correlation. For @math a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theory arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper and lower bound generalize beyond phase retrieval to measurements @math produced according to a generalized linear model. As a byproduct of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.
As previously mentioned, our analysis of spectral methods builds on the recent work of Lu and Li @cite_38 that compute the exact spectral threshold for a matrix of the form ) with @math . Here we generalize this result to signed pre-processing functions @math , and construct a function of this type that achieves the information-theoretic threshold for phase retrieval. Our proof indeed implies that non-negative pre-processing functions lead to an unavoidable gap with respect to the ideal threshold.
@cite_38
2593262341
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.