Nearly optimal bounds for the global geometric landscape of phase retrieval

Abstract

The phase retrieval problem is concerned with recovering an unknown signal $\mathbf{x}\in {\mathbb{R}}^{\mathbf{n}}$ from a set of magnitude-only measurements $y_j=|⟨{\mathbf{a}}_{\mathbf{j}},\mathbf{x}⟩|,\mathbf{j}=1,\dots ,\mathbf{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(n\log 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-Qu-Wright, in which the authors suggest that $O(n\log n)$ or even $O(n)$ is enough to guarantee the favorable geometric property.

arXiv comment32 pages

References in corpus (8)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• A Geometric Analysis of Phase Retrieval
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Phase Retrieval: An Overview of Recent Developments

Cited by in corpus (1)

• Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method