2017/08/20 by Mondelli, Marco, Montanari, Andrea · 3 citations
#FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.1708.05932
In phase retrieval we want to recover an unknown signal \boldsymbol x∈\mathbb Cd from n quadratic measurements of the form yi = |⟨\boldsymbol ai,\boldsymbol x⟩|2+wi where \boldsymbol ai∈ \mathbb Cd are known sensing vectors and wi is measurement noise. We ask the following weak recovery question: what is the minimum number of measurements n needed to produce an estimator \boldsymbol x(\boldsymbol y) that is positively correlated with the signal \boldsymbol x? We consider the case of Gaussian vectors \boldsymbol ai. 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 n≤ d-o(d) no estimator can do significantly better than random and achieve a strictly positive correlation. For n≥ 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-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 yi 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.