Optimal graph Laplacian

DOI10.1016/J.AUTOMATICA.2019.02.005MaRDI QIDQ1737851zbMATH OpenOpenAlexWikidataFDO

Authors Kazuhiro Sato

Publication date 24 April 2019

Published in Automatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1802.06482

zbMATH Keywords

convex optimizationdata-driven modelinggraph Laplacian

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35)

Abstract: This paper provides a construction method of the nearest graph Laplacian to a matrix identified from measurement data of graph Laplacian dynamics that include biochemical systems, synchronization systems, and multi-agent systems. We consider the case where the network structure, i.e., the connection relationship of edges of a given graph, is known. A problem of finding the nearest graph Laplacian is formulated as a convex optimization problem. Thus, our problem can be solved using interior point methods. However, the complexity of each iteration by interior point methods is $O(n^6)$, where $n$ is the number of nodes of the network. That is, if $n$ is large, interior point methods cannot solve our problem within a practical time. To resolve this issue, we propose a simple and efficient algorithm with the calculation complexity $O(n^2)$. Simulation experiments demonstrate that our method is useful to perform data-driven modeling of graph Laplacian dynamics.

Recommendations

• Convex optimization of graph Laplacian eigenvalues
• Distributed estimation of Laplacian eigenvalues via constrained consensus optimization problems
• Duality and nonlinear graph Laplacians
• An empirical comparison of graph Laplacian solvers
• Computing the smallest eigenpairs of the graph Laplacian

Cites work

• A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
• Collective dynamics of `small-world' networks
• Complex-linear invariants of biochemical networks
• Computing the nearest correlation matrix--a problem from finance
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Design of Optimal Sparse Feedback Gains via the Alternating Direction Method of Multipliers
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Dynamic mode decomposition of numerical and experimental data
• Graph theoretic methods in multiagent networks
• scientific article; zbMATH DE number 6678650 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Laplacian dynamics on general graphs
• Mathematical frameworks for oscillatory network dynamics in neuroscience
• Nearest stable system using successive convex approximations
• On computing the distance to stability for matrices using linear dissipative Hamiltonian systems
• Structural Monostability of Activation-Inhibition Boolean Networks
• Synchronization in complex networks of phase oscillators: a survey
• Synchronization in complex oscillator networks and smart grids

Cited in

(4)

• Optimal maximal graphs
• Optimization Algorithms for Graph Laplacian Estimation via ADMM and MM
• Laplacian pair-weight vector projection for semi-supervised learning
• Learning graph Laplacian with MCP

Describes a project that uses

Uses Software

• CVX

This page was built for publication: Optimal graph Laplacian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1737851)