mlsanityData to 7 Oct 2026

A Geometric Analysis of Phase Retrieval

arXiv 1602.06664 ↗First posted 22 Feb 2016cs.IT math.IT math.OCcited by 92

Not on the map. Why?

Abstract (arXiv)

Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of m measurements, yk = |mathbf ak^* mathbf x| for k = 1, dots, m, is it possible to recover mathbf x ∈ mathbbCn (i.e., length-n complex vector)? This **generalized phase retrieval** (GPR) problem is a fundamental task in various disciplines, and has been the subject of much recent investigation. Natural nonconvex heuristics often work remarkably well for GPR in practice, but lack clear theoretical explanations. In this paper, we take a step towards bridging this gap. We prove that when the measurement vectors mathbf ak's are generic (i.i.d. complex Gaussian) and the number of measurements is large enough (m ≥ C n log3 n), with high probability, a natural least-squares formulation for GPR has the following benign geometric structure: (1) there are no spurious local minimizers, and all global minimizers are equal to the target signal mathbf x, up to a global phase; and (2) the objective function has a negative curvature around each saddle point. This structure allows a number of iterative optimization methods to efficiently find a global minimizer, without special initialization. To corroborate the claim, we describe and analyze a second-order trust-region algorithm.

Key facts. Cited by 92 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 25; 2022: 20; 2023: 14; 2024: 12; 2025: 14; 2026: 6.

92 papers.

Sort:

By area:

  1. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 226
  2. 2022On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Featurescited by 97
  3. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  4. 2021An Unconstrained Layer-Peeled Perspective on Neural Collapsecited by 87
  5. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  6. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  7. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  8. 2021Near-Optimal Linear Regression under Distribution Shiftcited by 40
  9. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  10. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  11. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  12. 2021The loss landscape of deep linear neural networks: a second-order analysiscited by 24
38 more
  1. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  2. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  3. 2021Local convexity of the TAP free energy and AMP convergence for Z2-synchronizationcited by 15
  4. 2021Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priorscited by 14
  5. 2023Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGDcited by 14
  6. 2022Learning a Single Neuron for Non-monotonic Activation Functionscited by 13
  7. 2024A Global Geometric Analysis of Maximal Coding Rate Reductioncited by 13
  8. 2021Bandit Phase Retrievalcited by 12
  9. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  10. 2021Tractability from overparametrization: The example of the negative perceptroncited by 12
  11. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  12. 2021Active manifolds, stratifications, and convergence to local minima in nonsmooth optimizationcited by 11
  13. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  14. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  15. 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
  16. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  17. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  18. 2023Catapult Dynamics and Phase Transitions in Quadratic Netscited by 8
  19. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  20. 2021A first-order primal-dual method with adaptivity to local smoothnesscited by 7
  21. 2022Misspecified Phase Retrieval with Generative Priorscited by 7
  22. 2023Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learningcited by 7
  23. 2024The Role of the Time-Dependent Hessian in High-Dimensional Optimizationcited by 7
  24. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  25. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  26. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  27. 2025Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Modelscited by 6
  28. 2021Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descentcited by 5
  29. 2022Gradient descent provably escapes saddle points in the training of shallow ReLU networkscited by 5
  30. 2023A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Conditioncited by 5
  31. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  32. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 4
  33. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  34. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  35. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  36. 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
  37. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  38. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3

50 most cited of 92 All 92 (JSON)