convolutional phase retrieval via gradient descent

• DOI: 10.48550/arxiv.1712.00716
• Publication Date: 2020-03-01
• Authors: Qing Qu; Yuqian Zhang; Yonina C. Eldar; John Wright
• Keywords: FOS: Computer and information sciences; Computer Science - Information Theory; Information Theory (cs.IT); Machine Learning (stat.ML); Numerical Analysis (math.NA); 02 engineering and technology; Statistics - Computation; Statistics - Machine Learning; Optimization and Control (math.OC); FOS: Mathematics; 0202 electrical engineering, electronic engineering, information engineering; Mathematics - Numerical Analysis; Mathematics - Optimization and Control; Computation (stat.CO)

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<br/>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.<br/>