Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view

2025/06/23 by Stojnic, Mihailo · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2506.18279

Abstract

We analyze the relation between spectral initializers and theoretical limits of descending phase retrieval algorithms (dPR). In companion paper [104], for any sample complexity ratio, α, parametric manifold, \mathcal PM(α), is recognized as a critically important structure that generically determines dPRs abilities to solve phase retrieval (PR). Moreover, overlap between the algorithmic solution and the true signal is positioned as a key \mathcal PM's component. We here consider the so-called overlap optimal spectral initializers (OptSpins) as dPR's starting points and develop a generic Random duality theory (RDT) based program to statistically characterize them. In particular, we determine the functional structure of OptSpins and evaluate the starting overlaps that they provide for the dPRs. Since \mathcal PM's so-called flat regions are highly susceptible to local jitteriness and as such are key obstacles on dPR's path towards PR's global optimum, a precise characterization of the starting overlap allows to determine if such regions can be successfully circumvented. Through the presented theoretical analysis we observe two key points in that regard: (i) dPR's theoretical phase transition (critical α above which they solve PR) might be difficult to practically achieve as the \mathcal PM's flat regions are large causing the associated OptSpins to fall exactly within them; and (ii) Opting for so-called ``safer compression'' and slightly increasing α (by say 15%) shrinks flat regions and allows OptSpins to fall outside them and dPRs to ultimately solve PR. Numerical simulations are conducted as well and shown to be in an excellent agreement with theoretical predictions.

Citations

• Phase transition of descending phase retrieval algorithms
• Isolating the hard core of phaseless inference: the Phase selection formulation
• Deep ReLU networks -- injectivity capacity upper bounds
• Injectivity capacity of ReLU gates
• Fully lifted random duality theory
• Injectivity of ReLU networks: perspectives from statistical physics
• Constant-Expansion Suffices for Compressed Sensing with Generative Priors
• Exactly Computing the Local Lipschitz Constant of ReLU Networks
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• Fixed Point Analysis of Douglas-Rachford Splitting for Ptychography and Phase Retrieval
• Inverting Deep Generative models, One layer at a time
• Analysis of Spectral Methods for Phase Retrieval with Random Orthogonal\n Matrices
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
• Optimization of the Sherrington-Kirkpatrick Hamiltonian
• Phase Retrieval Under a Generative Prior
• A Precise Analysis of PhaseMax in Phase Retrieval
• Phase Retrieval via Linear Programming: Fundamental Limits and\n Algorithmic Improvements
• Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
• Phase Retrieval via Randomized Kaczmarz: Theoretical Guarantees
• Blind Demixing and Deconvolution at Near-Optimal Rate
• Phase Retrieval via Sparse Wirtinger Flow
• Compressed Sensing using Generative Models
• Phase Transitions of Spectral Initialization for High-Dimensional\n Nonconvex Estimation
• Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization
• Fully bilinear generic and lifted random processes comparisons
• Generic and lifted probabilistic comparisons -- max replaces minmax
• Box constrained ℓ₁ optimization in random linear systems -- asymptotics
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter\n Space via the Linear Program PhaseMax
• Vector Approximate Message Passing for the Generalized Linear Model
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Phase retrieval with random Gaussian sensing vectors by alternating\n projections
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as\n Solving Linear Systems
• Phase Retrieval with Application to Optical Imaging: A contemporary overview
• A small frame and a certificate of its injectivity
• PhaseLift is robust to a constant fraction of arbitrary errors
• Solving systems of phaseless equations via Kaczmarz methods: A proof of concept study
• Low rank matrix recovery from rank one measurements
• Robust Sparse Phase Retrieval Made Easy
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
• Phase Retrieval from Coded Diffraction Patterns
• Another look at the Gardner problem
• Phase Retrieval using Alternating Minimization
• Limits of local algorithms over sparse random graphs
• Regularly random duality
• Saving phase: Injectivity and stability for phase retrieval
• Saving phase: Injectivity and stability for phase retrieval
• Blind Deconvolution using Convex Programming
• Sparse Signal Recovery from Quadratic Measurements via Convex Programming
• Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns
• Phase Recovery, MaxCut and Complex Semidefinite Programming
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements\n via Convex Programming
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Phase Retrieval via Matrix Completion
• Various thresholds for ℓ₁-optimization in compressed sensing
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Reconstruction of an object from the modulus of its Fourier transform

Cited by

• Phase retrieval with rank d measurements -- descending algorithms phase transitions

Related

• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Phase transition of descending phase retrieval algorithms
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
• Random projections and the optimization of an algorithm for phase retrieval