# Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval

arXiv: https://arxiv.org/abs/1705.02356 · HTML: https://mlsanity.com/paper/1705.02356/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2017.

## Built on by (most cited first, 24 of 24)

- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization](https://mlsanity.com/paper/2108.11832/) (2021)
- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning](https://mlsanity.com/paper/2405.10289/) (2024)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions](https://mlsanity.com/paper/2308.16362/) (2023)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Convergence of Spectral Descent for Non-smooth Optimization](https://mlsanity.com/paper/2605.26977/) (2026)
- [Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization](https://mlsanity.com/paper/2206.14981/) (2022)
- [A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval](https://mlsanity.com/paper/2304.12522/) (2023)
- [FedDRO: Federated Compositional Optimization for Distributionally Robust Learning](https://mlsanity.com/paper/2311.12652/) (2023)
- [Acceleration and Implicit Regularization in Gaussian Phase Retrieval](https://mlsanity.com/paper/2311.12888/) (2023)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)
- [Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints](https://mlsanity.com/paper/2201.07657/) (2022)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)
- [An inexact LPA for DC composite optimization and application to matrix completions with outliers](https://mlsanity.com/paper/2303.16822/) (2023)
- [Moreau Envelope ADMM for Decentralized Weakly Convex Optimization](https://mlsanity.com/paper/2308.16752/) (2023)
- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)
- [Smoothed Robust Phase Retrieval](https://mlsanity.com/paper/2409.01570/) (2024)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)

## Abstract (arXiv)

We develop procedures, based on minimization of the composition f(x) = h(c(x)) of a convex function h and smooth function c, for solving random collections of quadratic equalities, applying our methodology to phase retrieval problems. We show that the prox-linear algorithm we develop can solve phase retrieval problems---even with adversarially faulty measurements---with high probability as soon as the number of measurements m is a constant factor larger than the dimension n of the signal to be recovered. The algorithm requires essentially no tuning---it consists of solving a sequence of convex problems---and it is implementable without any particular assumptions on the measurements taken. We provide substantial experiments investigating our methods, indicating the practical effectiveness of the procedures and showing that they succeed with high probability as soon as m / n ≥ 2 when the signal is real-valued.