## Abstract

Given nonlinear measurements y_{k} = |〈a_{k}, x〉| for k = 1.,m, is it possible to recover x ⋯ C^{n}? This generalized phase retrieval (GPR) problem is a fundamental task in various disciplines. Natural nonconvex methods often work remarkably well for GPR in practice, but lack clear theoretical explanations. In this paper, we take a step towards bridging this gap. We show that when the sensing vectors a_{k}'s are generic (i.i.d. complex Gaussian) and the number of measurements is large enough (m ≥ Cn log^{3} n), with high probability (w.h.p.), a natural least-squares formulation for GPR has the following benign geometric structure: (1) all local minimizers are global-they are the target signal x and its equivalent copies; and (2) the objective function has a negative directional curvature around each saddle point. Such structure allows a number of algorithmic possibilities for efficient global optimization. We describe a second-order trust-region algorithm that provably finds a global minimizer in polynomial time, from arbitrary initializations.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 2379-2383 |

Number of pages | 5 |

ISBN (Electronic) | 9781509018062 |

DOIs | |

State | Published - Aug 10 2016 |

Externally published | Yes |

Event | 2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2016-August |

ISSN (Print) | 2157-8095 |

### Other

Other | 2016 IEEE International Symposium on Information Theory, ISIT 2016 |
---|---|

Country/Territory | Spain |

City | Barcelona |

Period | 7/10/16 → 7/15/16 |

### Bibliographical note

Funding Information:This work was partially supported by funding from the Gordon and Betty Moore Foundation, the Alfred P. Sloan Foundation, and the grants ONR N00014-13-1-0492, NSF 1343282, NSF CCF 1527809, and NSF IIS 1546411

Publisher Copyright:

© 2016 IEEE.