Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

In phase retrieval, we want to recover an unknown signal $${{varvec{x}}}in {{mathbb {c}}}^d$$ from n quadratic measurements of the form $$y_i = |langle {{varvec{a}}}_i,{{varvec{x}}}rangle |^2+w_i$$ , where $${{varvec{a}}}_iin {{mathbb {c}}}^d$$ are known sensing vectors and $$w_i$$ is measurement noise. we ask the following weak recovery question: what is the minimum number of measurements n needed to produce an estimator $${hat{{{varvec{x}}}}}({{varvec{y}}})$$ that is positively correlated with the signal $${{varvec{x}}}$$ ? we consider the case of gaussian vectors $${{varvec{a}}}_i$$ . 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 $$nle d-o(d)$$ , no estimator can do significantly better than random and achieve a strictly positive correlation. for $$nge d+o(d)$$ , 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-theoretic 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 bound and lower bound generalize beyond phase retrieval to measurements $$y_i$$ produced according to a generalized linear model. as a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.