Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.03371 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910398440013824 |
|---|---|
| author | Sato, Kazuhiro Suzuki, Masato |
| author_facet | Sato, Kazuhiro Suzuki, Masato |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03371 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Nearest Graph Laplacian in Frobenius Norm Sato, Kazuhiro Suzuki, Masato Optimization and Control 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. |
| title | The Nearest Graph Laplacian in Frobenius Norm |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2404.03371 |