# The Nearest Graph Laplacian in Frobenius Norm

arXiv: https://arxiv.org/abs/2404.03371 · HTML: https://mlsanity.com/paper/2404.03371/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2024.

## Built on by (most cited first, 1 of 1)

- [NOMADS: Non-Markovian Optimization-based Modeling for Approximate Dynamics with Spatially-homogeneous Memory](https://mlsanity.com/paper/2409.19978/) (2024)

## Abstract (arXiv)

We address the problem of finding the nearest graph Laplacian to a given matrix, with the distance measured using the Frobenius norm. Specifically, for the directed graph Laplacian, we propose two novel algorithms by reformulating the problem as convex quadratic optimization problems with a special structure: one based on the active set method and the other on direct computation of Karush-Kuhn-Tucker (KKT) points. The proposed algorithms can be applied to system identification and model reduction problems involving Laplacian dynamics. We demonstrate that these algorithms possess lower time complexities and the finite termination property, unlike the interior point method and V-FISTA, the latter of which is an accelerated projected gradient method. Our numerical experiments confirm the effectiveness of the proposed algorithms.