×

Homotopy continuation for the spectra of persistent Laplacians. (English) Zbl 1494.55011

The Laplacian is a critical concept in network analysis and shape tasks. Given its limitation to a single scale of the data set, it was recently imbued with ideas from persistent homology, leading to the \(p\)-persistent \(q\)-combinatorial Laplacian of a simplicial complex. This construction, colloquially referred to as a persistent Laplacian can be shown to be intricately linked to multi-scale topological information, such as the persistent Betti numbers of a data set.
Motivated by the utility of persistent Laplacians, this paper presents a new way of calculating their spectral information, specifically, the roots of their characteristic polynomials, by homotopy continuation. Homotopy continuation addresses the problem of solving a system \(f\) of polynomial equations by starting with an easy-to-solve system \(g\), building a homotopy between \(f\) and \(g\), and, finally, tracking the roots of \(g\) to those of \(f\). The authors demonstrate the feasibility of this continuation method and provide empirical evidence of the utility of using spectral information from persistent Laplacians to characterise aromatic molecules, for instance.

MSC:

55N31 Persistent homology and applications, topological data analysis
55U10 Simplicial sets and complexes in algebraic topology
65H14 Numerical algebraic geometry
Full Text: DOI

References:

[1] E. L. Allgower; D. J. Bates; A. J. Sommese; C. W. Wampler, Solution of polynomial systems derived from differential equations, Computing, 76, 1-10 (2006) · Zbl 1086.65075 · doi:10.1007/s00607-005-0132-4
[2] D. N. Arnold, G. David, M. Filoche, D. Jerison and S. Mayboroda, Computing spectra without solving eigenvalue problems, SIAM J. Sci. Comput., 41 (2019), B69-B92. · Zbl 1420.81009
[3] D. J. Bates, I. A. Fotiou and P. Rostalski, A numerical algebraic geometry approach to nonlinear constrained optimal control, 46th IEEE Conference on Decision and Control, New Orleans, LA, 2007.
[4] D. J. Bates, J. D. Hauenstein, A. J. Sommese and C. W. Wampler, Bertini: Software for numerical algebraic geometry., Available from: https://bertini.nd.edu. · Zbl 1143.65344
[5] D. J. Bates, J. D. Hauenstein, A. J. Sommese and C. W. Wampler, Numerically Solving Polynomial Systems with Bertini, Software, Environments, and Tools, 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. · Zbl 1295.65057
[6] P. Breiding and S. Timme, HomotopyContinuation.jl: A package for homotopy continuation in Julia, in International Congress on Mathematical Software, Lecture Notes in Computer Science, 10931, Springer, 2018,458-465. · Zbl 1396.14003
[7] Z. Cang; L. Mu; K. Wu; K. Opron; K. Xia; G.-W. Wei, A topological approach for protein classification, Computational and Mathematical Biophysics, 3, 140-162 (2015) · Zbl 1347.92054 · doi:10.1515/mlbmb-2015-0009
[8] G. Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.), 46, 255-308 (2009) · Zbl 1172.62002 · doi:10.1090/S0273-0979-09-01249-X
[9] T. Chen, T.-L. Lee and T.-Y. Li, Hom4ps-3: A parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continuation methods, in Mathematical Software - ICMS 2014, Lecture Notes in Comput. Sci., 8592, Springer, Heidelberg, 2014,183-190. · Zbl 1434.65065
[10] H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010. · Zbl 1193.55001
[11] J. Friedman, Computing betti numbers via combinatorial Laplacians, Algorithmica, 21, 331-346 (1998) · Zbl 0911.57021 · doi:10.1007/PL00009218
[12] M. Gameiro; Y. Hiraoka; S. Izumi; M. Kramar; K. Mischaikow; V. Nanda, A topological measurement of protein compressibility, Jpn. J. Ind. Appl. Math., 32, 1-17 (2015) · Zbl 1320.55004 · doi:10.1007/s13160-014-0153-5
[13] T. E. Goldberg, Combinatorial Laplacians of simplicial complexes, Senior project, Bard College, 2002. Available from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3354&rep=rep1&type=pdf.
[14] E. Gross, B. Davis, K. L. Ho, D. J. Bates and H. A. Harrington, Numerical algebraic geometry for model selection and its application to the life sciences, J. Roy. Soc. Interface, 13 (2016).
[15] The GUDHI Project, GUDHI User and Reference Manual, 3.4.1 edition, GUDHI Editorial Board, 2021. Available from: https://gudhi.inria.fr/doc/3.4.1/.
[16] W. Hao; J. D. Hauenstein; B. Hu; Y. Liu; A. J. Sommese; Y.-T. Zhang, Multiple stable steady states of a reaction-diffusion model on zebrafish dorsal-ventral patterning, Discrete Contin. Dyn. Syst. Ser. S, 4, 1413-1428 (2011) · Zbl 1218.65043 · doi:10.3934/dcdss.2011.4.1413
[17] W. Hao, B. Hu and A. J. Sommese, Numerical algebraic geometry and differential equations, in Future Vision and Trends on Shapes, Geometry and Algebra, Springer Proc. Math. Stat., 84, Springer, London, 2014, 39-53. · Zbl 07905659
[18] C. R. Harris; K. J. Millman; S. J. van der Walt; R. Gommers; P. Virtanen, Array programming with NumPy, Nature, 585, 357-362 (2020) · doi:10.1038/s41586-020-2649-2
[19] J. Hauenstein; J. I. Rodriguez; B. Sturmfels, Maximum likelihood for matrices with rank constraints, J. Algebr. Stat., 5, 18-38 (2014) · Zbl 1345.62043 · doi:10.18409/jas.v5i1.23
[20] A. Leykin; F. Sottile, Galois groups of Schubert problems via homotopy computation, Math. Comp., 78, 1749-1765 (2009) · Zbl 1210.14064 · doi:10.1090/S0025-5718-09-02239-X
[21] L.-H. Lim, Hodge Laplacians on graphs, SIAM Rev., 62, 685-715 (2020) · Zbl 1453.05061 · doi:10.1137/18M1223101
[22] X. Liu, X. Wang, J. Wu and K. Xia, Hypergraph-based persistent cohomology (HPC) for molecular representations in drug design, Briefings in Bioinformatics, (2021), bbaa411.
[23] E. R. Love, B. Filippenko, V. Maroulas and G. Carlsson, Topological deep learning, preprint, arXiv: 2101.05778.
[24] F. Mémoli, Z. Wan and Y. Wang, Persistent Laplacians: Properties, algorithms and implications, preprint, arXiv: 2012.02808.
[25] Z. Meng, D. Vijay Anand, Y. Lu, J. Wu and K. Xia, Weighted persistent homology for biomolecular data analysis, Scientific Reports, 10 (2020), 1-15.
[26] F. Nasrin, C. Oballe, D. Boothe and V. Maroulas, Bayesian topological learning for brain state classification, 18th IEEE International Conference On Machine Learning And Applications (ICMLA), Boca Raton, FL, 2019.
[27] D. D. Nguyen; Z. Cang; G.-W. Wei, A review of mathematical representations of biomolecular data, Phys. Chem. Chem. Phys., 22, 4343-4367 (2020) · doi:10.1039/C9CP06554G
[28] Y. Ren; J. W. R. Martini; J. Torres, Decoupled molecules with binding polynomials of bidegree \((n, 2)\), J. Math. Biol., 78, 879-898 (2019) · Zbl 1416.82006 · doi:10.1007/s00285-018-1295-x
[29] I. Sgouralis; A. Nebenführ; V. Maroulas, A Bayesian topological framework for the identification and reconstruction of subcellular motion, SIAM J. Imaging Sci., 10, 871-899 (2017) · Zbl 1400.92310 · doi:10.1137/16M1095755
[30] A. J. Sommese and C. W. Wampler II, The Numerical Solution of Systems of Polynomials. Arising in Engineering and Science, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. · Zbl 1091.65049
[31] J. Townsend; C. P. Micucci; J. H. Hymel; V. Maroulas; K. D. Vogiatzis, Representation of molecular structures with persistent homology for machine learning applications in chemistry, Nature Communications, 11, 1-9 (2020) · doi:10.1038/s41467-020-17035-5
[32] J. Verschelde, Algorithm 795: Phcpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 251-276 (1999) · Zbl 0961.65047 · doi:10.1145/317275.317286
[33] C. W. Wampler; A. J. Sommese, Numerical algebraic geometry and algebraic kinematics, Acta Numer., 20, 469-567 (2011) · Zbl 1254.13031 · doi:10.1017/S0962492911000067
[34] R. Wang, D. D. Nguyen and G.-W. Wei, Persistent spectral graph, Int. J. Numer. Methods Biomed. Eng., 36 (2020), 27pp.
[35] R. Wang; R. Zhao; E. Ribando-Gros; J. Chen; Y. Tong; G.-W. Wei, HERMES: Persistent spectral graph software, Foundations of Data Science, 3, 67-97 (2020) · Zbl 1482.55001 · doi:10.3934/fods.2021006
[36] K. Xia; G.-W. Wei, Persistent homology analysis of protein structure, flexibility, and folding, Int. J. Numer. Methods Biomed. Eng., 30, 814-844 (2014) · doi:10.1002/cnm.2655
[37] X.-D. Zhang, The Laplacian eigenvalues of graphs: A survey, preprint, arXiv: 1111.2897.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.