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 (23)

• Guaranteed Matrix Completion via Non-convex Factorization
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Matrix Completion has No Spurious Local Minimum
• Nonconvex phase synchronization
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Distributions of Angles in Random Packing on Spheres
• Gradient Descent Converges to Minimizers
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• 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
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
• 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
• Phase retrieval for imaging problems
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• The minimal measurement number for low-rank matrices recovery

Cited by in corpus (15)

• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• 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
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
• 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