Phase Transitions

Here we will show two phase transition diagrams for the Wirtinger Flow (WF) algorithm.

Signal models

We consider two signal models:

Random low-pass signals.

Here, mathbf{x} is given by

$x[t]=sum_{k=-(M/2-1)}^{M/2} (X_k+iY_k) e^{2pi i(k-1)(t-1)/n},$

with M = n/8 and X_k and Y_k are i.i.d. mathcal{N}(0,1) .

Random Gaussian signals.

In this model, $mathbf{x} in C^n$ is a random complex Gaussian vector with i.i.d. entries of the form x[t] = X+iY with and distributed as mathcal{N}(0,1) ; this can be expressed as

${x}[t]=sum_{k=-(n/2-1)}^{n/2} (X_k+iY_k) e^{2pi i (k-1)(t-1)/n},$

where X_k and Y_k are are i.i.d. mathcal{N}(0,1/8) so that the low-pass model is a ‘bandlimited’ version of this high-pass random model (variances are adjusted so that the expected power is the same).

Measurement models

We perform simulations based on two different kinds of measurements:

Gaussian measurements.

We sample m=nL random complex Gaussian vectors $mathbf{a}_k$ and use measurements of the form $|mathbf{a}_k^*mathbf{x}|^2$ .

Coded diffraction patterns

We consider an acquisition model, where we collect data of the form

$y_r = left| sum_{t = 0}^{n-1} x[t] bar{d}_ell(t) e^{-i2pi k t/n} right|^2, quad r = (ell, k), quad begin{array}{l} 0 le k le n-1 1 le ell le L end{array};$

In particular, we focus on a random model in which the d_ell 's are i.i.d. distributed, each having i.i.d. entries sampled from a distribution . An example of an admissible random variable is d =b_1 b_2 , where b_1 and b_2 are independent and distributed as

We shall refer to this distribution as an octanary pattern since can take on eight distinct values.

Phase Transitions

Below, we set n=128 , and generate one signal of each type which will be used in all the experiments. The empirical probability of succcess is an average over 100 trials, where in each instance, we generate new random sampling vectors according to the Gaussian or CDP models. We declare a trial successful if the relative error of the reconstruction dist (hat{mathbf{x}},mathbf{x})/|mathbf{x}| falls below $10^{-5}$ .

Figure below shows that around 4.5n Gaussian phaseless measurements suffice for exact recovery with high probability via the Wirtinger flow algorithm. We also see that about six octanary patterns are sufficient.