TY - JOUR AB - In phase retrieval, we want to recover an unknown signal π‘₯βˆˆβ„‚π‘‘ from n quadratic measurements of the form 𝑦𝑖=|βŸ¨π‘Žπ‘–,π‘₯⟩|2+𝑀𝑖, where π‘Žπ‘–βˆˆβ„‚π‘‘ are known sensing vectors and 𝑀𝑖 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator π‘₯^(𝑦) that is positively correlated with the signal π‘₯? We consider the case of Gaussian vectors π‘Žπ‘Žπ‘–. 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 π‘›β‰€π‘‘βˆ’π‘œ(𝑑), no estimator can do significantly better than random and achieve a strictly positive correlation. For 𝑛β‰₯𝑑+π‘œ(𝑑), 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 𝑦𝑖 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. AU - Mondelli, Marco AU - Montanari, Andrea ID - 6662 IS - 3 JF - Foundations of Computational Mathematics TI - Fundamental limits of weak recovery with applications to phase retrieval VL - 19 ER -