Volume 37, Issue 4
The Global Landscape of Phase Retrieval I: Perturbed Amplitude Models

Jian-Feng Cai, Meng Huang, Dong Li & Yang Wang

Ann. Appl. Math., 37 (2021), pp. 437-512.

Published online: 2021-12

Export citation
  • Abstract

A fundamental task in phase retrieval is to recover an unknown signal $x\in\mathbb{R}^n$ from a set of magnitude-only measurements $y_i=|\langle a_i,x\rangle|,$ $ i=1,\cdots,m$. In this paper, we propose two novel perturbed amplitude models (PAMs) which have a non-convex and quadratic-type loss function. When the measurements $ a_i \in \mathbb{R}^n$ are Gaussian random vectors and the number of measurements $m\ge Cn$, we rigorously prove that the PAMs admit no spurious local minimizers with high probability, i.e., the target solution $ x$ is the unique local minimizer (up to a global phase) and the loss function has a negative directional curvature around each saddle point. Thanks to the well-tamed benign geometric landscape, one can employ the vanilla gradient descent method to locate the global minimizer $x$ (up to a global phase) without spectral initialization. We carry out extensive numerical experiments to show that the gradient descent algorithm with random initialization outperforms  state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed.

  • AMS Subject Headings

94A12, 65K10, 49K45

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{AAM-37-437, author = {Jian-Feng Cai , Meng Huang , Dong Li , and Wang , Yang}, title = {The Global Landscape of Phase Retrieval I: Perturbed Amplitude Models}, journal = {Annals of Applied Mathematics}, year = {2021}, volume = {37}, number = {4}, pages = {437--512}, abstract = {

A fundamental task in phase retrieval is to recover an unknown signal $x\in\mathbb{R}^n$ from a set of magnitude-only measurements $y_i=|\langle a_i,x\rangle|,$ $ i=1,\cdots,m$. In this paper, we propose two novel perturbed amplitude models (PAMs) which have a non-convex and quadratic-type loss function. When the measurements $ a_i \in \mathbb{R}^n$ are Gaussian random vectors and the number of measurements $m\ge Cn$, we rigorously prove that the PAMs admit no spurious local minimizers with high probability, i.e., the target solution $ x$ is the unique local minimizer (up to a global phase) and the loss function has a negative directional curvature around each saddle point. Thanks to the well-tamed benign geometric landscape, one can employ the vanilla gradient descent method to locate the global minimizer $x$ (up to a global phase) without spectral initialization. We carry out extensive numerical experiments to show that the gradient descent algorithm with random initialization outperforms  state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed.

}, issn = {}, doi = {https://doi.org/10.4208/aam.OA-2021-0009}, url = {http://global-sci.org/intro/article_detail/aam/20092.html} }
TY - JOUR T1 - The Global Landscape of Phase Retrieval I: Perturbed Amplitude Models AU - Jian-Feng Cai , AU - Meng Huang , AU - Dong Li , AU - Wang , Yang JO - Annals of Applied Mathematics VL - 4 SP - 437 EP - 512 PY - 2021 DA - 2021/12 SN - 37 DO - http://doi.org/10.4208/aam.OA-2021-0009 UR - https://global-sci.org/intro/article_detail/aam/20092.html KW - Phase retrieval, landscape analysis, non-convex optimization. AB -

A fundamental task in phase retrieval is to recover an unknown signal $x\in\mathbb{R}^n$ from a set of magnitude-only measurements $y_i=|\langle a_i,x\rangle|,$ $ i=1,\cdots,m$. In this paper, we propose two novel perturbed amplitude models (PAMs) which have a non-convex and quadratic-type loss function. When the measurements $ a_i \in \mathbb{R}^n$ are Gaussian random vectors and the number of measurements $m\ge Cn$, we rigorously prove that the PAMs admit no spurious local minimizers with high probability, i.e., the target solution $ x$ is the unique local minimizer (up to a global phase) and the loss function has a negative directional curvature around each saddle point. Thanks to the well-tamed benign geometric landscape, one can employ the vanilla gradient descent method to locate the global minimizer $x$ (up to a global phase) without spectral initialization. We carry out extensive numerical experiments to show that the gradient descent algorithm with random initialization outperforms  state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed.

Jian-Feng Cai , Meng Huang , Dong Li , and Wang , Yang. (2021). The Global Landscape of Phase Retrieval I: Perturbed Amplitude Models. Annals of Applied Mathematics. 37 (4). 437-512. doi:10.4208/aam.OA-2021-0009
Copy to clipboard
The citation has been copied to your clipboard