Solving Random Quadratic Systems of Equations Is Nearly as Easy as\n Solving Linear Systems

2015/05/19 by Yuxin Chen, Emmanuel J. Candès, Chen, Yuxin +1 · 20 citations
Computer Science · Environmental Science · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Numerical Analysis (math.NA) #Soil Geostatistics and Mapping #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1505.05114

openalex publication_date 2015/05/19 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28

Abstract

We consider the fundamental problem of solving quadratic systems of equations\nin n variables, where y_i = |\⟨ boldsymbola_i, boldsymbolx\n\⟩|², i = 1, \…, m and boldsymbolx \∈ \ℝⁿ is\nunknown. We propose a novel method, which starting with an initial guess\ncomputed by means of a spectral method, proceeds by minimizing a nonconvex\nfunctional as in the Wirtinger flow approach. There are several key\ndistinguishing features, most notably, a distinct objective functional and\nnovel update rules, which operate in an adaptive fashion and drop terms bearing\ntoo much influence on the search direction. These careful selection rules\nprovide a tighter initial guess, better descent directions, and thus enhanced\npractical performance. On the theoretical side, we prove that for certain\nunstructured models of quadratic systems, our algorithms return the correct\nsolution in linear time, i.e. in time proportional to reading the data\n boldsymbola_i and y_i as soon as the ratio m/n between the\nnumber of equations and unknowns exceeds a fixed numerical constant. We extend\nthe theory to deal with noisy systems in which we only have y_i \≈\n|\⟨ boldsymbola_i, boldsymbolx \⟩|² and prove that our\nalgorithms achieve a statistical accuracy, which is nearly un-improvable. We\ncomplement our theoretical study with numerical examples showing that solving\nrandom quadratic systems is both computationally and statistically not much\nharder than solving linear systems of the same size---hence the title of this\npaper. For instance, we demonstrate empirically that the computational cost of\nour algorithm is about four times that of solving a least-squares problem of\nthe same size.\n

Citations

• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

Cited by

• Near-optimal Reconfigurable Intelligent Surface Configuration: Blind Beamforming with Sensing
• Nuclear Ptychoscopy: A Ptychographic Framework for Nuclear Spectroscopy
• Community Recovery in Graphs with Locality
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Landscape Analysis of Simultaneous Blind Deconvolution and Phase Retrieval via Structured Low-Rank Tensor Recovery
• Recovery Performance of PhaseLift for Phase Retrieval from Coded Diffraction Patterns
• A convex program for bilinear inversion of sparse vectors
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• BranchHull: Convex bilinear inversion from the entrywise product of\n signals with known signs
• Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical\n Estimation
• A Smoothing Newton Method for Rank-one Matrix Recovery
• Convergence Analysis of Reshaped Wirtinger Flow with Random Initialization for Phase Retrieval
• Hybrid Precoding For Millimeter Wave MIMO Systems: A Matrix Factorization Approach
• Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow
• Sparse Signal Recovery From Quadratic Systems with Full-Rank Matrices
• The Condition Number in Phase Retrieval from Intensity Measurements
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
• Phase transition of descending phase retrieval algorithms
• A Scalable Factorization Approach for High-Order Structured Tensor Recovery

Related

• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Solving Almost all Systems of Random Quadratic Equations
• Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow
• Random Linear Systems with Quadratic Constraints: from Random Matrix Theory to replicas and back
• Testing systems of real quadratic equations for approximate solutions