Reshaped Wirtinger Flow for Solving Quadratic System of Equations
We study the problem of recovering a vector \bx\in \bbR^n$ from its magnitude measurements $y_i=\langle \ba_i, \bx\rangle| i=1, m$ Our work is along the line of the Wirtinger flow (WF) approach \citet{candes2015phase} which solves the problem by minimizing a nonconvex loss function via a gradient algorithm and can be shown to converge to a global optimal point under good initialization. In contrast to the smooth loss function used in WF, we adopt a nonsmooth but lower order loss function, and design a gradient like algorithm (referred to as reshaped WF) We show that for random Gaussian measurements, reshaped WF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is at the order of \cO(n) where $n$ is the dimension of the unknown \bx$ This improves the sample complexity of WF, and achieves the same sample complexity as truncated WF \citet{chen2015solving} but without truncation at gradient step. Furthermore, reshaped WF costs less computationally than WF, and runs faster numerically than both WF and truncated WF. Bypassing higher order variables in the loss function and truncations in the gradient loop, analysis of reshaped WF is simplified.
NIPS