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

Published in revised on IEEE Transactions on Information Theory, Arxiv, 2018

Recommended citation: Zhenzhen Li, Jian-Feng Cai, Ke Wei.

[ArXiv] [Code]

Abstract

The problem of finding a vector x which obeys a set of quadratic equations $|a^{T}_k x|^2=y_k$, $k=1,2,⋯,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≳n$. Moreover, the loss function always has a negative directional curvature around its saddle points.

Full Paper