A geometric analysis of generalized phase retrieval with Gaussian matrix measurements

Generalized phase retrieval aims at recovering an unknown signal x ∈ C n from quadratic measurements of the form x ∗ A j x , j=1 ,…,m, where measurement matrices A j are given. For real signal x ∈ R n , we show that when A j ∈ R n × n are independently drawn from standard Gaussian matrix distribution, the least squares loss function of generalized phase retrieval has a negative directional curvature around its saddle points and all its local minimizers are global minimizers with high probability under O( n) measurements. This benign geometric structure guarantees good performance of any algorithm that can escape saddle points. Especially, we present that the Gauss-Newton method is efficient in terms of convergence rate and empirical success rate, either in the case of spectral or random initialization.