Phase transition of descending phase retrieval algorithms
Not on the map. Why?
Abstract (arXiv)
We study theoretical limits of descending phase retrieval algorithms. Utilizing Random duality theory (RDT) we develop a generic program that allows statistical characterization of various algorithmic performance metrics. Through these we identify the concepts of parametric manifold and its funneling points as key mathematical objects that govern the underlying algorithms' behavior. An isomorphism between single funneling point manifolds and global convergence of descending algorithms is established. The structure and shape of the parametric manifold as well as its dependence on the sample complexity are studied through both plain and lifted RDT. Emergence of a phase transition is observed. Namely, as sample complexity increases, parametric manifold transitions from a multi to a single funneling point structure. This in return corresponds to a transition from the scenarios where descending algorithms generically fail to the scenarios where they succeed in solving phase retrieval. We also develop and implement a practical algorithmic variant that in a hybrid alternating fashion combines a barrier and a plain gradient descent. Even though the theoretical results are obtained for infinite dimensional scenarios (and consequently non-jittery parametric manifolds), we observe a strong agrement between theoretical and simulated phase transitions predictions for fairly small dimensions on the order of a few hundreds.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 50 of its 133 references that are in the map. First posted on arXiv 23 Jun 2025.
Builds on
50 of 133 references.
References · 50
- 2017Compressed Sensing using Generative Modelscited by 339
- 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
- 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
- 2020Exactly Computing the Local Lipschitz Constant of ReLU Networkscited by 102
- 2016A Geometric Analysis of Phase Retrievalcited by 92
- 2018Phase Retrieval Under a Generative Priorcited by 73
- 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
- 2013Phase Retrieval using Alternating Minimizationcited by 58
- 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
- 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
- 2015Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapsescited by 39
- 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
38 more
- 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
- 2019Inverting Deep Generative models, One layer at a timecited by 33
- 2016Solving Systems of Random Quadratic Equations via Truncated Amplitude Flowcited by 29
- 2013Phase Retrieval from Coded Diffraction Patternscited by 26
- 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
- 2016PhaseMax: Convex Phase Retrieval via Basis Pursuitcited by 25
- 2013Regularly random dualitycited by 24
- 2013Another look at the Gardner problemcited by 24
- 2013Limits of local algorithms over sparse random graphscited by 23
- 2015Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flowcited by 23
- 2015Local entropy as a measure for sampling solutions in Constraint Satisfaction Problemscited by 20
- 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
- 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
- 2021Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptroncited by 18
- 2023Fully lifted random duality theorycited by 18
- 2014Origin of the computational hardness for learning with binary synapsescited by 16
- 2016Phase retrieval with random Gaussian sensing vectors by alternating projectionscited by 15
- 2017Phase Retrieval via Randomized Kaczmarz: Theoretical Guaranteescited by 15
- 2013Lifting ℓ1-optimization strong and sectional thresholdscited by 13
- 2013Lifting/lowering Hopfield models ground state energiescited by 13
- 2017Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimizationcited by 13
- 2021Binary perceptron: efficient algorithms can find solutions in a rare well-connected clustercited by 13
- 2019Clustering of solutions in the symmetric binary perceptroncited by 12
- 2022Algorithms and Barriers in the Symmetric Binary Perceptron Modelcited by 12
- 2016Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxationcited by 11
- 2013Entropy landscape of solutions in the binary perceptron problemcited by 10
- 2023Injectivity of ReLU networks: perspectives from statistical physicscited by 10
- 2019On-Line Balancing of Random Inputscited by 9
- 2020Constant-Expansion Suffices for Compressed Sensing with Generative Priorscited by 9
- 2021Tight Lipschitz Hardness for Optimizing Mean Field Spin Glassescited by 9
- 2013Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithmscited by 8
- 2024Hardness of sampling solutions from the Symmetric Binary Perceptroncited by 8
- 2024Some easy optimization problems have the overlap-gap propertycited by 5
- 2015PhaseLift is robust to a constant fraction of arbitrary errorscited by 4
- 2024Injectivity capacity of ReLU gatescited by 4
- 2016An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMaxcited by 3
- 2019Fixed Point Analysis of Douglas-Rachford Splitting for Ptychography and Phase Retrievalcited by 3
- 2024Deep ReLU networks -- injectivity capacity upper boundscited by 3
Built on by
Not cited yet.