Aditya Viswanathan

Mark Iwen, Aditya Viswanathan, Yang Wang

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} \left( d \log^4 d \right)$-time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals ${\bf x}$ satisfying a natural flatness (i.e., non-sparsity) 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. 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.

Mark A. Iwen, Brian Preskitt, Rayan Saab et al.

We improve a phase retrieval approach that uses correlation-based measurements with compactly supported measurement masks [27]. The improved algorithm admits deterministic measurement constructions together with a robust, fast recovery algorithm that consists of solving a system of linear equations in a lifted space, followed by finding an eigenvector (e.g., via an inverse power iteration). Theoretical reconstruction error guarantees from [27] are improved as a result for the new and more robust reconstruction approach proposed herein. Numerical experiments demonstrate robustness and computational efficiency that outperforms competing approaches on large problems. Finally, we show that this approach also trivially extends to phase retrieval problems based on windowed Fourier measurements.

Jade Larriva-Latt, Angela Morrison, Alison Radgowski et al.

Certain applications such as Magnetic Resonance Imaging (MRI) require the reconstruction of functions from Fourier spectral data. When the underlying functions are piecewise-smooth, standard Fourier approximation methods suffer from the Gibbs phenomenon - with associated oscillatory artifacts in the vicinity of edges and an overall reduced order of convergence in the approximation. This paper proposes an edge-augmented Fourier reconstruction procedure which uses only the first few Fourier coefficients of an underlying piecewise-smooth function to accurately estimate jump information and then incorporate it into a Fourier partial sum approximation. We provide both theoretical and empirical results showing the improved accuracy of the proposed method, as well as comparisons demonstrating superior performance over existing state-of-the-art sparse optimization-based methods. Extensions of the proposed techniques to functions of several variables are also addressed preliminarily. All code used to generate the results in this report are made publicly available.

Sami Merhi, Aditya Viswanathan, Mark Iwen

A novel phase retrieval method, motivated by ptychographic imaging, is proposed for the approximate recovery of a compactly supported specimen function $f:\mathbb{R}\rightarrow\mathbb{C}$ from its continuous short time Fourier transform (STFT) spectrogram measurements. The method, partially inspired by the well known PhaseLift algorithm, is based on a lifted formulation of the infinite dimensional problem which is then later truncated for the sake of computation. Numerical experiments demonstrate the promise of the proposed approach.

Mark Iwen, Aditya Viswanathan, Yang Wang

In this short note we propose a simple two-stage sparse phase retrieval strategy that uses a near-optimal number of measurements, and is both computationally efficient and robust to measurement noise. In addition, the proposed strategy is fairly general, allowing for a large number of new measurement constructions and recovery algorithms to be designed with minimal effort.