Can I read Sparsification of the regularized magnetic Laplacian with multi-type spanning forests on EtoBox?

Sparsification of the regularized magnetic Laplacian with multi-type spanning forests by Fanuel, Michaël; Bardenet, Rémi is a scholarly article available to read on EtoBox.

What is Sparsification of the regularized magnetic Laplacian with multi-type spanning forests about?

In this paper, we consider a ${\rm U}(1)$-connection graph, that is, a graph where each oriented edge is endowed with a unit modulus complex number that is conjugated under orientation flip. A natural replacement for the combinatorial Laplacian is then the magnetic Laplacian, an Hermitian matrix that includes information about the graph's connection. Magnetic Laplacians appear, e.g., in the problem of angular synchronization. In the context of large and dense graphs, we study here sparsifiers of the magnetic Laplacian $\Delta$, i.e., spectral approximations based on subgraphs with few edges. Our approach relies on sampling multi-type spanning forests (MTSFs) using a custom determinantal point process, a probability distribution over edges that favours diversity. In a word, an MTSF is a spanning subgraph whose connected components are either trees or cycle-rooted trees. The latter partially capture the angular inconsistencies of the connection graph, and thus provide a way to compress the information contained in the connection. Interestingly, when the connection graph has weakly inconsistent cycles, samples from the determinantal point process under consideration can be obtained \`

Author

Fanuel, Michaël; Bardenet, Rémi

Published

2022

Language

EN