A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval

Abstract

We analyze continuous-time mirror descent applied to sparse phase retrieval, which is the problem of recovering sparse signals from a set of magnitude-only measurements. We apply mirror descent to the unconstrained empirical risk minimization problem (batch setting), using the square loss and square measurements. We provide a convergence analysis of the algorithm in this non-convex setting and prove that, with the hypentropy mirror map, mirror descent recovers any $k$-sparse vector ${\mathbf{x}}^{\star }\in {\mathbb{R}}^n$ with minimum (in modulus) non-zero entry on the order of $\Vert {\mathbf{x}}^{\star }{\Vert }_2/\sqrt{k}$ from $k^2$ Gaussian measurements, modulo logarithmic terms. This yields a simple algorithm which, unlike most existing approaches to sparse phase retrieval, adapts to the sparsity level, without including thresholding steps or adding regularization terms. Our results also provide a principled theoretical understanding for Hadamard Wirtinger flow [58], as Euclidean gradient descent applied to the empirical risk problem with Hadamard parametrization can be recovered as a first-order approximation to mirror descent in discrete time.

References in corpus (11)

• DGM: A deep learning algorithm for solving partial differential equations
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Implicit Regularization for Optimal Sparse Recovery
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• A Continuous-Time View of Early Stopping for Least Squares
• Hadamard Wirtinger Flow for Sparse Phase Retrieval