mlsanityData to 14 Oct 2026

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

arXiv 2506.18282 ↗First posted 23 Jun 2025stat.ML cs.IT cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Companion paper [118] developed a powerful Random duality theory (RDT) based analytical program to statistically characterize performance of descending phase retrieval algorithms (dPR) (these include all variants of gradient descents and among them widely popular Wirtinger flows). We here generalize the program and show how it can be utilized to handle rank d positive definite phase retrieval (PR) measurements (with special cases d=1 and d=2 serving as emulations of the real and complex phase retrievals, respectively). In particular, we observe that the minimal sample complexity ratio (number of measurements scaled by the dimension of the unknown signal) which ensures dPR's success exhibits a phase transition (PT) phenomenon. For both plain and lifted RDT we determine phase transitions locations. To complement theoretical results we implement a log barrier gradient descent variant and observe that, even in small dimensional scenarios (with problem sizes on the order of 100), the simulated phase transitions are in an excellent agreement with the theoretical predictions.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 50 of its 132 references that are in the map. First posted on arXiv 23 Jun 2025.

Builds on

50 of 132 references.

References · 50

  1. 2017Compressed Sensing using Generative Modelscited by 339
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  4. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  5. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  6. 2020Exactly Computing the Local Lipschitz Constant of ReLU Networkscited by 102
  7. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  8. 2016A Geometric Analysis of Phase Retrievalcited by 92
  9. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  10. 2018Phase Retrieval Under a Generative Priorcited by 73
  11. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  12. 2013Phase Retrieval using Alternating Minimizationcited by 58
38 more
  1. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  2. 2015Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapsescited by 39
  3. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  4. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  5. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  6. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
  7. 2019Inverting Deep Generative models, One layer at a timecited by 33
  8. 2016Solving Systems of Random Quadratic Equations via Truncated Amplitude Flowcited by 29
  9. 2013Phase Retrieval from Coded Diffraction Patternscited by 26
  10. 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
  11. 2016PhaseMax: Convex Phase Retrieval via Basis Pursuitcited by 25
  12. 2013Regularly random dualitycited by 24
  13. 2013Another look at the Gardner problemcited by 24
  14. 2013Limits of local algorithms over sparse random graphscited by 23
  15. 2015Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flowcited by 23
  16. 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23
  17. 2015Local entropy as a measure for sampling solutions in Constraint Satisfaction Problemscited by 20
  18. 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
  19. 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
  20. 2023Fully lifted random duality theorycited by 18
  21. 2016Phase retrieval with random Gaussian sensing vectors by alternating projectionscited by 15
  22. 2017Phase Retrieval via Randomized Kaczmarz: Theoretical Guaranteescited by 15
  23. 2013Lifting ℓ1-optimization strong and sectional thresholdscited by 13
  24. 2013Lifting/lowering Hopfield models ground state energiescited by 13
  25. 2017Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimizationcited by 13
  26. 2019Clustering of solutions in the symmetric binary perceptroncited by 12
  27. 2016Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxationcited by 11
  28. 2023Injectivity of ReLU networks: perspectives from statistical physicscited by 10
  29. 2020Constant-Expansion Suffices for Compressed Sensing with Generative Priorscited by 9
  30. 2013Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithmscited by 8
  31. 2015PhaseLift is robust to a constant fraction of arbitrary errorscited by 4
  32. 2018Geometric Invariants for Sparse Unknown View Tomographycited by 4
  33. 20203D unknown view tomography via rotation invariantscited by 4
  34. 2024Injectivity capacity of ReLU gatescited by 4
  35. 2016An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMaxcited by 3
  36. 2019Fixed Point Analysis of Douglas-Rachford Splitting for Ptychography and Phase Retrievalcited by 3
  37. 2024Deep ReLU networks -- injectivity capacity upper boundscited by 3
  38. 2019On phase retrieval via matrix completion and the estimation of low rank PSD matricescited by 1

Built on by

Not cited yet.