# Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2016.

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

- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [On the use of deep learning for phase recovery](https://mlsanity.com/paper/2308.00942/) (2023)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork](https://mlsanity.com/paper/2101.04348/) (2021)
- [On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning](https://mlsanity.com/paper/2405.10289/) (2024)
- [Stable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2405.10754/) (2024)
- [Total Least Squares Phase Retrieval](https://mlsanity.com/paper/2102.00927/) (2021)
- [Provable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2210.09248/) (2022)
- [Unique Bispectrum Inversion for Signals with Finite Spectral/Temporal Support](https://mlsanity.com/paper/2111.06479/) (2021)
- [Optimizing Intermediate Representations of Generative Models for Phase Retrieval](https://mlsanity.com/paper/2205.15617/) (2022)
- [One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility](https://mlsanity.com/paper/2303.09594/) (2023)
- [A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval](https://mlsanity.com/paper/2304.12522/) (2023)
- [A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval](https://mlsanity.com/paper/2409.04733/) (2024)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)
- [Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems](https://mlsanity.com/paper/2111.03237/) (2021)
- [Convex Augmentation for Total Variation Based Phase Retrieval](https://mlsanity.com/paper/2205.00834/) (2022)
- [Smoothed Robust Phase Retrieval](https://mlsanity.com/paper/2409.01570/) (2024)
- [Global convergence of gradient descent for phase retrieval](https://mlsanity.com/paper/2410.09990/) (2024)
- [Quaternionic Reweighted Amplitude Flow for Phase Retrieval in Image Reconstruction](https://mlsanity.com/paper/2501.02180/) (2025)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view](https://mlsanity.com/paper/2506.18279/) (2025)
- [Phase retrieval with rank d measurements -- descending algorithms phase transitions](https://mlsanity.com/paper/2506.18282/) (2025)

## Abstract (arXiv)

This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector bmx from a system of quadratic equations of the form yi=|langlebmai,bmxrangle|2, where bmai's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adopts the amplitude-based empirical loss function, and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors bmx and bmai's are real-valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.