10.1007/s10208-018-9395-y
Mondelli, Marco
Marco
Mondelli0000-0002-3242-7020
Montanari, Andrea
Andrea
Montanari
Fundamental limits of weak recovery with applications to phase retrieval
Springer
2019
2019-07-22T13:23:48Z
2019-11-14T08:43:35Z
journal_article
https://research-explorer.app.ist.ac.at/record/6662
https://research-explorer.app.ist.ac.at/record/6662.json
1708.05932
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.