
-
Previous Article
Learning landmark geodesics using the ensemble Kalman filter
- FoDS Home
- This Issue
- Next Article
Homotopy continuation for the spectra of persistent Laplacians
1. | Department of Mathematics, Michigan State University, MI 48824, USA |
2. | Department of Mathematics, Department of Electrical and Computer Engineering, Department of Biochemistry and Molecular Biology, Michigan State University, MI 48824, USA |
The $ p $-persistent $ q $-combinatorial Laplacian defined for a pair of simplicial complexes is a generalization of the $ q $-combinatorial Laplacian. Given a filtration, the spectra of persistent combinatorial Laplacians not only recover the persistent Betti numbers of persistent homology but also provide extra multiscale geometrical information of the data. Paired with machine learning algorithms, the persistent Laplacian has many potential applications in data science. Seeking different ways to find the spectrum of an operator is an active research topic, becoming interesting when ideas are originated from multiple fields. In this work, we explore an alternative approach for the spectrum of persistent Laplacians. As the eigenvalues of a persistent Laplacian matrix are the roots of its characteristic polynomial, one may attempt to find the roots of the characteristic polynomial by homotopy continuation, and thus resolving the spectrum of the corresponding persistent Laplacian. We consider a set of simple polytopes and small molecules to prove the principle that algebraic topology, combinatorial graph, and algebraic geometry can be integrated to understand the shape of data.
References:
[1] |
E. L. Allgower, D. J. Bates, A. J. Sommese and C. W. Wampler,
Solution of polynomial systems derived from differential equations, Computing, 76 (2006), 1-10.
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.
doi: 10.1137/17M1156721. |
[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.
doi: 10.1109/CDC.2007.4434470. |
[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. |
[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.
doi: 10.1137/1.9781611972702. |
[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.
doi: 10.1007/978-3-319-96418-8_54. |
[7] |
Z. Cang, L. Mu, K. Wu, K. Opron, K. Xia and G.-W. Wei,
A topological approach for protein classification, Computational and Mathematical Biophysics, 3 (2015), 140-162.
doi: 10.1515/mlbmb-2015-0009. |
[8] |
G. Carlsson,
Topology and data, Bull. Amer. Math. Soc. (N.S.), 46 (2009), 255-308.
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.
doi: 10.1007/978-3-662-44199-2_30. |
[10] |
H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010.
doi: 10.1090/mbk/069. |
[11] |
J. Friedman,
Computing betti numbers via combinatorial Laplacians, Algorithmica, 21 (1998), 331-346.
doi: 10.1007/PL00009218. |
[12] |
M. Gameiro, Y. Hiraoka, S. Izumi, M. Kramar, K. Mischaikow and V. Nanda,
A topological measurement of protein compressibility, Jpn. J. Ind. Appl. Math., 32 (2015), 1-17.
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).
doi: 10.1098/rsif.2016.0256. |
[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 and Y.-T. Zhang,
Multiple stable steady states of a reaction-diffusion model on zebrafish dorsal-ventral patterning, Discrete Contin. Dyn. Syst. Ser. S, 4 (2011), 1413-1428.
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.
doi: 10.1007/978-1-4471-6461-6_3. |
[18] |
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers and P. Virtanen,
Array programming with NumPy, Nature, 585 (2020), 357-362.
doi: 10.1038/s41586-020-2649-2. |
[19] |
J. Hauenstein, J. I. Rodriguez and B. Sturmfels,
Maximum likelihood for matrices with rank constraints, J. Algebr. Stat., 5 (2014), 18-38.
doi: 10.18409/jas.v5i1.23. |
[20] |
A. Leykin and F. Sottile,
Galois groups of Schubert problems via homotopy computation, Math. Comp., 78 (2009), 1749-1765.
doi: 10.1090/S0025-5718-09-02239-X. |
[21] |
L.-H. Lim,
Hodge Laplacians on graphs, SIAM Rev., 62 (2020), 685-715.
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.
doi: 10.1093/bib/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.
doi: 10.1038/s41598-019-55660-3. |
[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.
doi: 10.1109/ICMLA.2019.00205. |
[27] |
D. D. Nguyen, Z. Cang and G.-W. Wei,
A review of mathematical representations of biomolecular data, Phys. Chem. Chem. Phys., 22 (2020), 4343-4367.
doi: 10.1039/C9CP06554G. |
[28] |
Y. Ren, J. W. R. Martini and J. Torres,
Decoupled molecules with binding polynomials of bidegree $(n, 2)$, J. Math. Biol., 78 (2019), 879-898.
doi: 10.1007/s00285-018-1295-x. |
[29] |
I. Sgouralis, A. Nebenführ and V. Maroulas,
A Bayesian topological framework for the identification and reconstruction of subcellular motion, SIAM J. Imaging Sci., 10 (2017), 871-899.
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.
doi: 10.1142/5763. |
[31] |
J. Townsend, C. P. Micucci, J. H. Hymel, V. Maroulas and K. D. Vogiatzis,
Representation of molecular structures with persistent homology for machine learning applications in chemistry, Nature Communications, 11 (2020), 1-9.
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 (1999), 251-276.
doi: 10.1145/317275.317286. |
[33] |
C. W. Wampler and A. J. Sommese,
Numerical algebraic geometry and algebraic kinematics, Acta Numer., 20 (2011), 469-567.
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.
doi: 10.1002/cnm.3376. |
[35] |
R. Wang, R. Zhao, E. Ribando-Gros, J. Chen, Y. Tong and G.-W. Wei,
HERMES: Persistent spectral graph software, Foundations of Data Science, 3 (2020), 67-97.
doi: 10.3934/fods.2021006. |
[36] |
K. Xia and G.-W. Wei,
Persistent homology analysis of protein structure, flexibility, and folding, Int. J. Numer. Methods Biomed. Eng., 30 (2014), 814-844.
doi: 10.1002/cnm.2655. |
[37] |
X.-D. Zhang, The Laplacian eigenvalues of graphs: A survey, preprint, arXiv: 1111.2897. |
show all references
References:
[1] |
E. L. Allgower, D. J. Bates, A. J. Sommese and C. W. Wampler,
Solution of polynomial systems derived from differential equations, Computing, 76 (2006), 1-10.
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.
doi: 10.1137/17M1156721. |
[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.
doi: 10.1109/CDC.2007.4434470. |
[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. |
[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.
doi: 10.1137/1.9781611972702. |
[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.
doi: 10.1007/978-3-319-96418-8_54. |
[7] |
Z. Cang, L. Mu, K. Wu, K. Opron, K. Xia and G.-W. Wei,
A topological approach for protein classification, Computational and Mathematical Biophysics, 3 (2015), 140-162.
doi: 10.1515/mlbmb-2015-0009. |
[8] |
G. Carlsson,
Topology and data, Bull. Amer. Math. Soc. (N.S.), 46 (2009), 255-308.
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.
doi: 10.1007/978-3-662-44199-2_30. |
[10] |
H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010.
doi: 10.1090/mbk/069. |
[11] |
J. Friedman,
Computing betti numbers via combinatorial Laplacians, Algorithmica, 21 (1998), 331-346.
doi: 10.1007/PL00009218. |
[12] |
M. Gameiro, Y. Hiraoka, S. Izumi, M. Kramar, K. Mischaikow and V. Nanda,
A topological measurement of protein compressibility, Jpn. J. Ind. Appl. Math., 32 (2015), 1-17.
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).
doi: 10.1098/rsif.2016.0256. |
[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 and Y.-T. Zhang,
Multiple stable steady states of a reaction-diffusion model on zebrafish dorsal-ventral patterning, Discrete Contin. Dyn. Syst. Ser. S, 4 (2011), 1413-1428.
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.
doi: 10.1007/978-1-4471-6461-6_3. |
[18] |
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers and P. Virtanen,
Array programming with NumPy, Nature, 585 (2020), 357-362.
doi: 10.1038/s41586-020-2649-2. |
[19] |
J. Hauenstein, J. I. Rodriguez and B. Sturmfels,
Maximum likelihood for matrices with rank constraints, J. Algebr. Stat., 5 (2014), 18-38.
doi: 10.18409/jas.v5i1.23. |
[20] |
A. Leykin and F. Sottile,
Galois groups of Schubert problems via homotopy computation, Math. Comp., 78 (2009), 1749-1765.
doi: 10.1090/S0025-5718-09-02239-X. |
[21] |
L.-H. Lim,
Hodge Laplacians on graphs, SIAM Rev., 62 (2020), 685-715.
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.
doi: 10.1093/bib/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.
doi: 10.1038/s41598-019-55660-3. |
[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.
doi: 10.1109/ICMLA.2019.00205. |
[27] |
D. D. Nguyen, Z. Cang and G.-W. Wei,
A review of mathematical representations of biomolecular data, Phys. Chem. Chem. Phys., 22 (2020), 4343-4367.
doi: 10.1039/C9CP06554G. |
[28] |
Y. Ren, J. W. R. Martini and J. Torres,
Decoupled molecules with binding polynomials of bidegree $(n, 2)$, J. Math. Biol., 78 (2019), 879-898.
doi: 10.1007/s00285-018-1295-x. |
[29] |
I. Sgouralis, A. Nebenführ and V. Maroulas,
A Bayesian topological framework for the identification and reconstruction of subcellular motion, SIAM J. Imaging Sci., 10 (2017), 871-899.
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.
doi: 10.1142/5763. |
[31] |
J. Townsend, C. P. Micucci, J. H. Hymel, V. Maroulas and K. D. Vogiatzis,
Representation of molecular structures with persistent homology for machine learning applications in chemistry, Nature Communications, 11 (2020), 1-9.
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 (1999), 251-276.
doi: 10.1145/317275.317286. |
[33] |
C. W. Wampler and A. J. Sommese,
Numerical algebraic geometry and algebraic kinematics, Acta Numer., 20 (2011), 469-567.
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.
doi: 10.1002/cnm.3376. |
[35] |
R. Wang, R. Zhao, E. Ribando-Gros, J. Chen, Y. Tong and G.-W. Wei,
HERMES: Persistent spectral graph software, Foundations of Data Science, 3 (2020), 67-97.
doi: 10.3934/fods.2021006. |
[36] |
K. Xia and G.-W. Wei,
Persistent homology analysis of protein structure, flexibility, and folding, Int. J. Numer. Methods Biomed. Eng., 30 (2014), 814-844.
doi: 10.1002/cnm.2655. |
[37] |
X.-D. Zhang, The Laplacian eigenvalues of graphs: A survey, preprint, arXiv: 1111.2897. |


















[1] |
Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006 |
[2] |
Alex L Castro, Wyatt Howard, Corey Shanbrom. Bridges between subriemannian geometry and algebraic geometry: Now and then. Conference Publications, 2015, 2015 (special) : 239-247. doi: 10.3934/proc.2015.0239 |
[3] |
M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks and Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201 |
[4] |
Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. |
[5] |
Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485 |
[6] |
Daniel Maxin, Fabio Augusto Milner. The effect of nonreproductive groups on persistent sexually transmitted diseases. Mathematical Biosciences & Engineering, 2007, 4 (3) : 505-522. doi: 10.3934/mbe.2007.4.505 |
[7] |
Francis Michael Russell, J. C. Eilbeck. Persistent mobile lattice excitations in a crystalline insulator. Discrete and Continuous Dynamical Systems - S, 2011, 4 (5) : 1267-1285. doi: 10.3934/dcdss.2011.4.1267 |
[8] |
Daniel Amin, Mikael Vejdemo-Johansson. Intrinsic disease maps using persistent cohomology. Foundations of Data Science, 2021 doi: 10.3934/fods.2021008 |
[9] |
Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1 |
[10] |
Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307 |
[11] |
Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021 |
[12] |
Piermarco Cannarsa, Patrick Martinez, Judith Vancostenoble. Persistent regional null contrillability for a class of degenerate parabolic equations. Communications on Pure and Applied Analysis, 2004, 3 (4) : 607-635. doi: 10.3934/cpaa.2004.3.607 |
[13] |
Xue Yang, Xinglong Wu. Wave breaking and persistent decay of solution to a shallow water wave equation. Discrete and Continuous Dynamical Systems - S, 2016, 9 (6) : 2149-2165. doi: 10.3934/dcdss.2016089 |
[14] |
Mario E. Chávez-Gordillo, Bernardo San Martín, Jaime Vera. Persistent singular attractors arising from singular cycle under symmetric conditions. Discrete and Continuous Dynamical Systems, 2011, 30 (3) : 671-685. doi: 10.3934/dcds.2011.30.671 |
[15] |
Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093 |
[16] |
Peter Haïssinsky, Kevin M. Pilgrim. An algebraic characterization of expanding Thurston maps. Journal of Modern Dynamics, 2012, 6 (4) : 451-476. doi: 10.3934/jmd.2012.6.451 |
[17] |
Aihua Li. An algebraic approach to building interpolating polynomial. Conference Publications, 2005, 2005 (Special) : 597-604. doi: 10.3934/proc.2005.2005.597 |
[18] |
Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 |
[19] |
Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031 |
[20] |
Doston Jumaniyozov, Ivan Kaygorodov, Abror Khudoyberdiyev. The algebraic classification of nilpotent commutative algebras. Electronic Research Archive, 2021, 29 (6) : 3909-3993. doi: 10.3934/era.2021068 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]