Wirtinger Flow (WF)

We are interested in solving quadratic equations of the form

 y_r=|langlemathbf{a}_r, mathbf{z}rangle|^2,quad r=1,2,ldots,m,

where mathbf{z}in C^n is the decision variable, mathbf{a}_rin C^n are known sampling vectors, and y_rin R are observed measurements.

We introduce an approach to phase retrieval based on non-convex optimization as well as a solution algorithm, which has two components:

(1) a careful initialization obtained by means of a spectral method
(2) a series of updates refining this initial estimate by iteratively applying a novel update rule, much like in a gradient descent scheme.

We refer to the combination of these two steps, introduced in reverse order below, as the Wirtinger flow (WF) algorithm.

Minimization of a non-convex objective

A solution to the generalized phase retrieval problem is any solution to

 minimize quad f(mathbf{z}):=frac{1}{2m}sum_{r=1}^m left(y_r-|mathbf{a}_r^*mathbf{z}|^2right)^2, quad mathbf{z} in C^n.

Our approach to solve the above optimization problem is simply stated: start with an initialization mathbf{z}_0, and for tau = 0, 1, 2, ldots, inductively define

 mathbf{z}_{tau+1}=mathbf{z}_tau-frac{mu_{tau+1}}{|mathbf{z}_0|^2}left(frac{1}{m}sum_{r=1}^mleft(|mathbf{a}_r^*mathbf{z}|^2-y_rright)left(mathbf{a}_rmathbf{a}_r^*right)mathbf{z}right):=mathbf{z}_tau-frac{mu_{tau+1}}{|mathbf{z}_0|^2}nabla f(mathbf{z}_tau).

Initialization via a spectral method

We propose computing the initial guess mathbf{z}_0 via a spectral method, detailed in the algorithm below.