On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization

Abstract

Studying the landscape of nonconvex cost function 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 to study 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(\mathbf{\theta })=\frac{1}{2}{\sum }_{1\le i,j\le n}{a}_{ij}(1-\cos ({\theta }_i-{\theta }_j))$ associated to an underlying network and exploring the relationship between the existence of local minima and network topology. This function arises naturally in Burer-Monteiro method applied to ${\mathbb{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 the minimizer of the energy function is unique up to a global translation under deterministic dense graphs and Erdős-Rényi 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 ${\mathbb{Z}}_2$ synchronization and shed light on the robustness of nonconvex optimization algorithms against certain types of so-called monotone adversaries. Numerical simulations are performed to illustrate our results.

arXiv comment27 pages, 6 figures

References in corpus (20)

• Synchronization in complex networks
• The Kuramoto model in complex networks
• Synchronization in Complex Oscillator Networks and Smart Grids
• A Simpler Approach to Matrix Completion
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Frequency synchronization in random oscillator network
• Low-rank optimization for semidefinite convex problems
• Nonconvex phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Near-optimal bounds for phase synchronization
• When Are Nonconvex Problems Not Scary?
• Matrix Completion from a Few Entries
• The Non-convex Geometry of Low-rank Matrix Optimization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Algebraic Geometrization of the Kuramoto Model: Equilibria and Stability Analysis
• Message-passing algorithms for synchronization problems over compact groups
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Synchronization in the random field Kuramoto model on complex networks
• Structured Local Optima in Sparse Blind Deconvolution

Cited by in corpus (1)

• The nonsmooth landscape of blind deconvolution