ON THE LANDSCAPE OF SYNCHRONIZATION NETWORKS: A PERSPECTIVE FROM NONCONVEX OPTIMIZATION

Studying the landscape of nonconvex cost functions is key towards a better understanding of optimization algorithms widely used in signal processing, statistics, and machine learning. Meanwhile, the famous Kuramoto model has been an important mathematical model for studying the synchronization phenomena of coupled oscillators over various network topologies. In this paper, we bring together these two seemingly unrelated objects by investigating the optimization landscape of a nonlinear function E(theta) = 1/2 Sigma(1 <= i,j <= n) a(ij)(1 - cos(theta(i) - theta(j))) associated with an underlying net- work and exploring the relationship between the existence of local minima and the network topology. This function arises naturally in the Burer-Monteiro method applied to Z(2) synchronization as well as matrix completion on the torus. Moreover, it corresponds to the energy function of the homogeneous Kuramoto model on complex networks for coupled oscillators. We prove that the minimizer of the energy function is unique up to a global translation under deterministic dense graphs and Erdos-Renyi random graphs with tools from optimization and random matrix theory. Consequently, the stable equilibrium of the corresponding homogeneous Kuramoto model is unique and the basin of attraction for the synchronous state of these coupled oscillators is the whole phase space minus a set of measure zero. In addition, our results address when the Burer-Monteiro method recovers the ground truth exactly from highly incomplete observations in Z(2) synchronization and shed light on the robustness of nonconvex optimization algorithms with respect to certain types of so-called monotone adversaries. Numerical simulations are performed to illustrate our results.