Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations

Abstract

We study the phase retrieval problem, which solves quadratic system of equations, i.e., recovers a vector $\mathbf{x}\in {\mathbb{R}}^n$ from its magnitude measurements $y_i=|⟨{\mathbf{a}}_i,\mathbf{x}⟩|,i=1,...,m$. We develop a gradient-like algorithm (referred to as RWF representing reshaped Wirtinger flow) by minimizing a nonconvex nonsmooth loss function. In comparison with existing nonconvex Wirtinger flow (WF) algorithm \cite{candes2015phase}, although the loss function becomes nonsmooth, it involves only the second power of variable and hence reduces the complexity. We show that for random Gaussian measurements, RWF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is on the order of $n$, the dimension of the unknown $\mathbf{x}$. This improves the sample complexity of WF, and achieves the same sample complexity as truncated Wirtinger flow (TWF) \cite{chen2015solving}, but without truncation in gradient loop. Furthermore, RWF costs less computationally than WF, and runs faster numerically than both WF and TWF. We further develop the incremental (stochastic) reshaped Wirtinger flow (IRWF) and show that IRWF converges linearly to the true signal. We further establish performance guarantee of an existing Kaczmarz method for the phase retrieval problem based on its connection to IRWF. We also empirically demonstrate that IRWF outperforms existing ITWF algorithm (stochastic version of TWF) as well as other batch algorithms.

Part of this draft is accepted to NIPS 2016

References in corpus (12)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Matrix Completion has No Spurious Local Minimum
• Gradient Descent Converges to Minimizers
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Phase Retrieval via Incremental Truncated Wirtinger Flow
• Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems

Cited by in corpus (14)

• Low Rank Phase Retrieval
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Convergence of the randomized Kaczmarz method for phase retrieval
• Convolutional Phase Retrieval via Gradient Descent
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Solving Almost all Systems of Random Quadratic Equations
• Phase Retrieval via Sparse Wirtinger Flow
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Provable Low Rank Phase Retrieval