Convolutional Phase Retrieval via Gradient Descent

Abstract

We study the convolutional phase retrieval problem, of recovering an unknown signal $\mathbf{x}\in {\mathbb{C}}^n$ from $m$ measurements consisting of the magnitude of its cyclic convolution with a given kernel $\mathbf{a}\in {\mathbb{C}}^m$. This model is motivated by applications such as channel estimation, optics, and underwater acoustic communication, where the signal of interest is acted on by a given channel/filter, and phase information is difficult or impossible to acquire. We show that when $\mathbf{a}$ is random and the number of observations $m$ is sufficiently large, with high probability $\mathbf{x}$ can be efficiently recovered up to a global phase shift using a combination of spectral initialization and generalized gradient descent. The main challenge is coping with dependencies in the measurement operator. We overcome this challenge by using ideas from decoupling theory, suprema of chaos processes and the restricted isometry property of random circulant matrices, and recent analysis of alternating minimization methods.

64 pages , 9 figures, appeared in NeurIPS 2017. Accepted at IEEE Transactions on Information Theory. This is the final (minor) update: fixed typos and grammar issues

References in corpus (7)

• Simple, Efficient, and Neural Algorithms for Sparse Coding
• Fast matrix completion without the condition number
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Optimization Methods for Convolutional Sparse Coding
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Structured Local Optima in Sparse Blind Deconvolution
• Efficient Dictionary Learning with Gradient Descent

Cited by in corpus (8)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Structured Local Optima in Sparse Blind Deconvolution
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization