Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations

Abstract

The problem of finding a vector $x$ which obeys a set of quadratic equations $|a_k^{\top }x{|}^2=y_k$, $k=1,\cdots ,m$, plays an important role in many applications. In this paper we consider the case when both $x$ and $a_k$ are real-valued vectors of length $n$. A new loss function is constructed for this problem, which combines the smooth quadratic loss function with an activation function. Under the Gaussian measurement model, we establish that with high probability the target solution $x$ is the unique local minimizer (up to a global phase factor) of the new loss function provided $m\gtrsim n$. Moreover, the loss function always has a negative directional curvature around its saddle points.

References in corpus (18)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• An algebraic characterization of injectivity in phase retrieval
• Matrix Completion has No Spurious Local Minimum
• Nonconvex phase synchronization
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Analyzing Tensor Power Method Dynamics in Overcomplete Regime
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• The local convexity of solving systems of quadratic equations
• Deep Learning without Poor Local Minima
• Convergence of the randomized Kaczmarz method for phase retrieval
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity

Cited by in corpus (1)

• Scalable Incremental Nonconvex Optimization Approach for Phase Retrieval