Fundamental limits of weak recovery with applications to phase retrieval

M. Mondelli, A. Montanari, Foundations of Computational Mathematics 19 (2019) 703–773.


Journal Article | Published | English
Author
;
Abstract
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.
Publishing Year
Date Published
2019-06-01
Journal Title
Foundations of Computational Mathematics
Volume
19
Issue
3
Page
703-773
eISSN
IST-REx-ID

Cite this

Mondelli M, Montanari A. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 2019;19(3):703-773. doi:10.1007/s10208-018-9395-y
Mondelli, M., & Montanari, A. (2019). Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics, 19(3), 703–773. https://doi.org/10.1007/s10208-018-9395-y
Mondelli, Marco, and Andrea Montanari. β€œFundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics 19, no. 3 (2019): 703–73. https://doi.org/10.1007/s10208-018-9395-y.
M. Mondelli and A. Montanari, β€œFundamental limits of weak recovery with applications to phase retrieval,” Foundations of Computational Mathematics, vol. 19, no. 3, pp. 703–773, 2019.
Mondelli M, Montanari A. 2019. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 19(3), 703–773.
Mondelli, Marco, and Andrea Montanari. β€œFundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics, vol. 19, no. 3, Springer, 2019, pp. 703–73, doi:10.1007/s10208-018-9395-y.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1708.05932

Search this title in

Google Scholar