Top

Published in:

2016 | OriginalPaper | Chapter

Optimal Cycles for Persistent Homology Via Linear Programming

Authors : Emerson G. Escolar, Yasuaki Hiraoka

Published in: Optimization in the Real World

Publisher: Springer Japan

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this work, we discuss the problem of finding optimal cycles for homology groups of simplicial complexes and for persistent homology of filtrations. We review the linear programming formulation of the optimal homologous cycle problem and its extension to allow for multiple cycles. By inserting these linear programming problems into the persistent homology algorithm, we are able to compute an optimal cycle, that has been optimized at birth, for every persistent interval in the persistent diagram.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Optimal Turbine Allocation for Offshore and Onshore Wind Farms

next chapter Optimal Battery Control for Smart Grid Nodes

Berman, H.M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T.N., Weissig, H., Shindyalov, I.N., Bourne, P.E.: The Protein Data Bank. Nucleic Acids Res. 28(1), 235–242 (2000)

Cgal, Computational Geometry Algorithms Library: http://www.cgal.org

Chen, C., Freedman, D.: Hardness results for homology localization. Discrete Comput. Geom. 45(3), 425–448 (2011)MATHMathSciNetCrossRef

Chen, C., Freedman, D.: Measuring and computing natural generators for homology groups. Comput. Geom. 43(2), 169–181 (2010)MATHMathSciNetCrossRef

Dey, T.K., Hirani, A.N., Krishnamoorthy, B.: Optimal homologous cycles, total unimodularity, and linear programming. SIAM J. Comput. 40(4), 1026–1044 (2011)MATHMathSciNetCrossRef

Dey, T.K., Sun, J., Wang, Y.: Approximating cycles in a shortest basis of the first homology group from point data. Inverse Prob. 27(12) (2011)

Edelsbrunner, H.: Weighted alpha shapes. Technical report, Department of Computer Science, University of Illinois at Urbana-Champaign (1992)

Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002)MATHMathSciNetCrossRef

Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1038–1046. SIAM (2005)

10.

Escolar, E.G., Yasuaki H.: Computing optimal cycles of homology groups. In: Nishii, R., et al. (eds.) A Mathematical Approach to Research Problems of Science and Technology, pp. 101–118. Springer, Japan (2014)

11.

Fermi, G., Perutz, M.F., Shaanan, B., Fourme, R.: The crystal structure of human deoxyhaemoglobin at 1.74 Å resolution. J. Mol. Biol. 175(2), 159–174 (1984)CrossRef

12.

International Business Machines Corp.: IBM ILOG CPLEX Optimization Studio. http://www-03.ibm.com/software/products/en/ibmilogcpleoptistud/

13.

Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, New York (2004)MATHCrossRef

14.

Munkres, J.: Elements of Algebraic Topology. The Benjamin/Cummings Publishing Company Inc, Menlo Park, California (1984)MATH

15.

Nakamura, T., Hiraoka, Y., Hirata, A., Escolar, E.G., Matsue, K., Nishiura, Y.: Description of Medium-Range Order in Amorphous Structures by Persistent Homology. arxiv.org/abs/1501.03611

16.

Salkin, H.M., Mathur, K.: Foundations of Integer Programming. North Holland, New York (1989)

17.

Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249–274 (2005)MATHMathSciNetCrossRef

Title: Optimal Cycles for Persistent Homology Via Linear Programming
Authors: Emerson G. Escolar
Yasuaki Hiraoka
Publisher: Springer Japan
Book: Optimization in the Real World
Print ISBN: 978-4-431-55419-6

Electronic ISBN: 978-4-431-55420-2

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-4-431-55420-2_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partners