Convolutional Phase Retrieval via Gradient Descent
arXiv:1712.00716
Abstract
We study the convolutional phase retrieval problem, of recovering an unknown signal from measurements consisting of the magnitude of its cyclic convolution with a given kernel . 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 is random and the number of observations is sufficiently large, with high probability 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.
arXiv comment64 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 (31)
- Guaranteed Matrix Completion via Non-convex Factorization
- Self-Calibration and Biconvex Compressive Sensing
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Nonconvex phase synchronization
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- A Partial Derandomization of PhaseLift using Spherical Designs
- When Are Nonconvex Problems Not Scary?
- Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank- Updates
- Simple, Efficient, and Neural Algorithms for Sparse Coding
- New Algorithms for Learning Incoherent and Overcomplete Dictionaries
- Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
- Fast matrix completion without the condition number
- Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
- A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
- Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
- More Algorithms for Provable Dictionary Learning
- Complete Dictionary Recovery over the Sphere
- Optimization Methods for Convolutional Sparse Coding
- An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
- Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
- A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
- RIP-like Properties in Subsampled Blind Deconvolution
- Greed is Super: A Fast Algorithm for Super-Resolution
- Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
- Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
- Fast Exact Matrix Completion with Finite Samples
- Through the Haze: a Non-Convex Approach to Blind Gain Calibration for Linear Random Sensing Models
- Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing
- Structured Local Optima in Sparse Blind Deconvolution
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
- 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 -regularization
- The Global Optimization Geometry of Shallow Linear Neural Networks
- Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization