Nearly optimal bounds for the global geometric landscape of phase retrieval

Abstract

<p>The phase retrieval problem is concerned with recovering an unknown signal x∈Cn from a set of magnitude-only measurements yj=|⟨aj,x⟩|,j=1,…,m. A natural least squares formulation can be used to solve this problem efficiently even with random initialization, despite its non-convexity of the loss function. One way to explain this surprising phenomenon is the benign geometric landscape: (1) all local minimizers are global; and (2) the objective function has a negative curvature around each saddle point and local maximizer. In this paper, we show that m=O(nlog⁡n) Gaussian random measurements are sufficient to guarantee the loss function of a commonly used estimator has such benign geometric landscape with high probability. This is a step toward answering the open problem given by Sun <em>et al</em> (2018 <em>Found. Comput. Math.</em><strong>18</strong> 1131–98), in which the authors suggest that O(nlog⁡n) or even <em>O</em>(<em>n</em>) is enough to guarantee the favorable geometric property.</p>