Fast Phase Retrieval from Local Correlation Measurements

Abstract

We develop a fast phase retrieval method which can utilize a large class of local phaseless correlation-based measurements in order to recover a given signal ${\bf x} \in \mathbb{C}^d$ (up to an unknown global phase) in near-linear $\mathcal{O} ( d \log^4 d )$-time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals ${\bf x}$ satisfying a natural flatness (i.e., nonsparsity) condition for a particular choice of deterministic correlation-based measurements. A randomized version of these same measurements is then shown to provide nonuniform probabilistic recovery guarantees for arbitrary signals ${\bf x} \in \mathbb{C}^d$. Numerical experiments demonstrate the method's speed, accuracy, and robustness in practice---all code is made publicly available. In its simplest form, our proposed phase retrieval method employs a modified lifting scheme akin to the one utilized by the well-known PhaseLift algorithm. In particular, it interprets quadratic magnitude measurements of ${\mathbf x}$ as linear measurements of a restricted set of lifted variables, $x_i \overline{x_j}$, for $| j - i | < \delta \ll d$. This leads to a linear system involving a total of $(2 \delta-1)d$ unknown lifted variables, all of which can then be solved for using only $\mathcal{O}(\delta d)$ measurements. Once these lifted variables, $x_i \overline{x_j}$ for $| j - i | < \delta \ll d$, have been recovered, a fast angular synchronization method can then be used to propagate the local phase difference information they provide across the entire vector in order to estimate the (relative) phases of every entry of ${\mathbf x}$. In addition, the lifted variables corresponding to $x_j \overline{x_j} = |x_j|^2$ automatically provide magnitude estimates for each entry, $x_j$, of ${\mathbf x}$. The proposed phase retrieval method then approximates ${\mathbf x}$ by carefully combining these entrywise phase and magnitude estimates. Finally, we conclude by developing an extension of the proposed method to the sparse phase retrieval problem; specifically, we demonstrate a sublinear-time compressive phase retrieval algorithm which is guaranteed to recover a given $s$-sparse vector ${\bf x} \in \mathbb{C}^d$ with high probability in just $\mathcal{O}(s \log^5 s \cdot \log d)$-time using only $\mathcal{O}(s \log^4 s \cdot \log d)$ magnitude measurements. In doing so we demonstrate the existence of compressive phase retrieval algorithms with near-optimal linear-in-sparsity runtime complexities.