Provable Phase Retrieval with Mirror Descent

Abstract

In this paper, we consider the problem of phase retrieval, which consists of recovering an $n$-dimensional real vector from the magnitude of its $m$ linear measurements. We propose a mirror descent (or Bregman gradient descent) algorithm based on a wisely chosen Bregman divergence, hence allowing to remove the classical global Lipschitz continuity requirement on the gradient of the non-convex phase retrieval objective to be minimized. We apply the mirror descent for two random measurements: the \iid standard Gaussian and those obtained by multiple structured illuminations through Coded Diffraction Patterns (CDP). For the Gaussian case, we show that when the number of measurements $m$ is large enough, then with high probability, for almost all initializers, the algorithm recovers the original vector up to a global sign change. For both measurements, the mirror descent exhibits a local linear convergence behaviour with a dimension-independent convergence rate. Our theoretical results are finally illustrated with various numerical experiments, including an application to the reconstruction of images in precision optics.

References in corpus (9)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• A Geometric Analysis of Phase Retrieval
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• The Numerics of Phase Retrieval
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
• Transversality and alternating projections for nonconvex sets
• Quantitative convergence analysis of iterated expansive, set-valued mappings
• Local Linear Convergence of Approximate Projections onto Regularized Sets
• Convergence Analysis of the Relaxed Douglas-Rachford Algorithm