The persistent Laplacian of non-branching complexes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912423166869504 |
|---|---|
| author | Botnan, Magnus Bakke Dong, Rui |
| author_facet | Botnan, Magnus Bakke Dong, Rui |
| contents | Non-branching matrices are real matrices with entries in $\{-1,0,1\}$, where each row contains at most two non-zero entries. Such matrices naturally arise in the study of Laplacians of pseudomanifolds and cubical complexes. We show that a basis for the kernel of a non-branching matrix can be computed in near-linear time. Especially, the basis has the special property that the supports of all the column vectors in it are disjoint with each other. Building on this result, we show that the up persistent Laplacian can be computed in near-linear time for a pair of such spaces and its eigenvalues can be more efficiently computed via computing singular values. In addition to that, we analyze the arithmetic operations of up persistent Laplacian with respect to a non-branching filtration. Furthermore, we show that the up persistent Laplacian of $q$-non-branching simplicial complexes can be represented as the Laplacian of an associated hypergraph, thus providing a higher-dimensional generalization of the Kron reduction, as well as a Cheeger-type inequality. Finally, we highlight the efficiency of our method on image data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16741 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The persistent Laplacian of non-branching complexes Botnan, Magnus Bakke Dong, Rui Algebraic Topology 62R40, 55N31, 05C50, 05C65, 05C85 Non-branching matrices are real matrices with entries in $\{-1,0,1\}$, where each row contains at most two non-zero entries. Such matrices naturally arise in the study of Laplacians of pseudomanifolds and cubical complexes. We show that a basis for the kernel of a non-branching matrix can be computed in near-linear time. Especially, the basis has the special property that the supports of all the column vectors in it are disjoint with each other. Building on this result, we show that the up persistent Laplacian can be computed in near-linear time for a pair of such spaces and its eigenvalues can be more efficiently computed via computing singular values. In addition to that, we analyze the arithmetic operations of up persistent Laplacian with respect to a non-branching filtration. Furthermore, we show that the up persistent Laplacian of $q$-non-branching simplicial complexes can be represented as the Laplacian of an associated hypergraph, thus providing a higher-dimensional generalization of the Kron reduction, as well as a Cheeger-type inequality. Finally, we highlight the efficiency of our method on image data. |
| title | The persistent Laplacian of non-branching complexes |
| topic | Algebraic Topology 62R40, 55N31, 05C50, 05C65, 05C85 |
| url | https://arxiv.org/abs/2408.16741 |