Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-30T15:33:43.611Z Has data issue: false hasContentIssue false
  • English
  • Français

Topological pattern recognition for point cloud data*

Published online by Cambridge University Press:  12 May 2014

Gunnar Carlsson
Gunnar Carlsson*
Affiliation:
Department of Mathematics, Stanford University, CA 94305, USA, E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we discuss the adaptation of the methods of homology from algebraic topology to the problem of pattern recognition in point cloud data sets. The method is referred to as persistent homology, and has numerous applications to scientific problems. We discuss the definition and computation of homology in the standard setting of simplicial complexes and topological spaces, then show how one can obtain useful signatures, called barcodes, from finite metric spaces, thought of as sampled from a continuous object. We present several different cases where persistent homology is used, to illustrate the different ways in which the method can be applied.

Type
Research Article
Information
Acta Numerica , Volume 23 , May 2014 , pp. 289 - 368
Copyright
Copyright © Cambridge University Press 2014 

Footnotes

*

Colour online for monochrome figures available at journals.cambridge.org//anu.

References

REFERENCES

Abergel, A.et al. (2011), ‘Planck early results XXIV: Dust in the diffuse interstellar medium and the galactic halo’, Astron. Astrophys. 536, A24.Google Scholar
Adler, R. (1981), The Geometry of Random Fields, Wiley Series in Probability and Mathematical Statistics.Google Scholar
Adler, R. and Taylor, J. (2007), Random Fields and Geometry, Springer Monographs in Mathematics.Google Scholar
Adler, R., Bobrowski, O., Borman, M., Subag, E. and Weinberger, S. (2010), Persistent homology for random fields and complexes. In Borrowing Strength: Theory Powering Applications: A Festschrift for Lawrence D. Brown, Vol. 6, pp. 124–143.Google Scholar
Bak, A. and Lerner, M. (2014), in preparation.Google Scholar
Bardeen, J., Bond, J., Kaiser, N. and Szalay, A. (1986), ‘The statistics of peaks of Gaussian random fields’, Astrophys. J. 304, 15–61.CrossRefGoogle Scholar
Bennett, C., Hill, R., Hinshaw, G., Nolta, M., Odegard, N., Page, L., Spergel, D., Weiland, J., Wright, E., Halpern, M., Jarosik, N., Kogut, A., Limon, M., Meyer, S., Tucker, G. and Wollack, E. (2003), ‘First-year Wilkinson Microwave Anisotropy Probe (WMAP)* observations: Foreground emission’, Astrophys. J. Supplement Series 148, 97.Google Scholar
Blumberg, A., Gal, I., Mandell, M. and Pancia, M. (2013), Robust statistics, hypothesis testing, and confidence intervals for persistent homology on metric measure spaces. arXiv:1206.4581Google Scholar
Bonnet, O. (1848), ‘Mémoire sur la théorie generale des surfaces’, Journal de l'Ecole Polytechnique 19, 1–146.Google Scholar
Buneman, P. (1974), ‘A note on the metric properties of trees’, J. Combin. Theory B 17, 48–50.Google Scholar
Burago, D., Burago, Y. and Ivanov, S. (2001), A Course in Metric Geometry, Vol. 33 of Graduate Studies in Mathematics, AMS.Google Scholar
Carlsson, G. (2009), ‘Topology and data’, Bull. Amer. Math. Soc. 46, 255–308.Google Scholar
Carlsson, G. and de Silva, V. (2010), ‘Zigzag persistence’, Found. Comput. Math. 10, 367–405.Google Scholar
Carlsson, G. and Zomorodian, A. (2009), ‘The theory of multidimensional persistence’, Discrete Comput. Geom. 42, 71–93.CrossRefGoogle Scholar
Carlsson, G., Ishkhanov, T., de Silva, V. and Zomorodian, A. (2008), ‘On the local behavior of spaces of natural images’, Internat. J. Computer Vision 76, 1–12.Google Scholar
Carlsson, G., de Silva, V. and Morozov, D. (2009), Zigzag persistent homology and real-valued functions. In Proc. 25th Annual Symposium on Computational Geometry, ACM, pp. 247–256.Google Scholar
Carlsson, G., Zomorodian, A., Collins, A. and Guibas, L. (2005), ‘Persistence barcodes for shapes’, Internat. J. Shape Modeling 11, 149.Google Scholar
Chan, J., Carlsson, G. and Rabadan, R. (2013), ‘Topology of viral evolution’, Proc. Nat. Acad. Sci. 110, 18566–18571.Google Scholar
Chazal, F., Cohen-Steiner, D., Guibas, L., Memoli, F. and Oudot, S. (2009), ‘Gromov-Hausdorff stable signatures for shapes using persistence. In Eurographics Symposium on Geometry Processing 2009. Computer Graphics Forum 28, 1393–1403.Google Scholar
Chazal, F., Cohen-Steiner, D. and Merigot, Q. (2011), ‘Geometric inference for probability measures’, Found. Comput. Math. 11, 733–751.Google Scholar
Cohen-Steiner, D., Edelsbrunner, H. and Harer, J. (2007), ‘Stability of persistence diagrams’, Discrete Comput. Geom. 37, 103–120.Google Scholar
Cohen-Steiner, D., Edelsbrunner, H., Harer, J. and Mileyko, Y. (2010), ‘Lipschitz functions have Lp-stable persistence’, Found. Comput. Math. 10, 127–139.Google Scholar
Dalbec, J. (1999), ‘Multisymmetric functions’, Beiträge Algebra Geom. 40, 27–51Google Scholar
Derksen, H. and Weyman, J. (2005), ‘Quiver representations’, Notices Amer. Math. Soc. 52, 200–206.Google Scholar
Donoho, D. (1999), ‘Wedgelets: Nearly minimax estimation of edges’, Ann. Statist. 27, 859–897.Google Scholar
Doolittle, W. (1999), ‘Phylogenetic classification and the universal tree’, Science 284 (5423), 2124–2128.Google Scholar
Drummond, A., Nicholls, F., Rodrigo, A. and Solomon, W. (2002), ‘Estimating mutation parameters, population history, and genealogy simultaneously from temporally spaced sequence data’, Genetics 161, 1307–1320.Google Scholar
Edelsbrunner, H., Letscher, D. and Zomorodian, A. (2002), ‘Topological persistence and simplification’, Discrete Comput. Geom. 28, 511–533CrossRefGoogle Scholar
Eilenberg, S. (1944), ‘Singular homology theory’, Ann. of Math. 45, 407–447.Google Scholar
Euler, L. (1741), ‘Solutio problematis ad geometriam situs pertinentis’, Commen-tarii Academiae Scientiarum Petropolitanae 8, 128–140.Google Scholar
Euler, L. (1758 a), ‘Elementa doctrinae solidorum’, Novi Commentarii Academiae Scientiarum Petropolitanae 4, 109–140. Opera Omnia (1) 26, 72–93.Google Scholar
Euler, L. (1758 b), ‘Demonstratio nonnullarum insignium proprietatum quibus solida hedris planis inclusa sunt praedita’, Novi Commentarii Academiae Scien-tiarum Petropolitanae 4, 140–160. Opera Omnia (1) 26, 94–108.Google Scholar
Felsenstein, J. (2004), Inferring Phylogenies, Sinauer Associates, Sunderland, MA.Google Scholar
Fréchet, M. (1944), ‘L'intégrale abstraite d'une fonction abstraite d'une variable abstraite et son application à la moyenne d'un élément aléatoire de nature quelconque’ Rev. Sci. 82, 483–512.Google Scholar
Frechet, M. (1948), ‘Les elements aratoires de nature quelconque dans un espace distancié’ Ann. Inst. Henri Poincaré 10, 215–310.Google Scholar
Gabriel, P. (1972), ‘Unzerlegbare Darstellungen I’, Manuscr. Math. 6, 71–103.Google Scholar
Greven, A., Pfafelhuber, P. and Winter, A. (2009), ‘Convergence in distribution of random metric measure spaces’, Probab. Theory Rel. Fields 145, 285–322.Google Scholar
Gott, J., Dickinson, M. and Melott, A. (1986), ‘The sponge-like topology of large-scale structure in the universe’, Astrophys. J. 306, 341–357.Google Scholar
Hamilton, A., Gott, J. and Weinberg, D. (1986), ‘The topology of the large-scale structure of the universe’, Astrophys. J. 309, 1–12.Google Scholar
Hartigan, J. (1975), Clustering Algorithms, Wiley Series in Probability and Mathematical Statistics.Google Scholar
Hatcher, A. (2002), Algebraic Topology, Cambridge University Press.Google Scholar
van Hateren, J. and van der Schaaf, A. (1998), ‘Independent component filters of natural images compared with simple cells in primary visual cortex’, Proc. R. Soc. Lond. B 265, 359–366.Google Scholar
Huchra, J., Jarrett, T., Skrutskie, M., Cutri, R., Schneider, S. and Macri, L. (2005), The 2MASS redshift survey and low galactic latitude large-scale structure. In Nearby Large-Scale Structures and the Zone of Avoidance (Fairall, K.P. and Woudt, P. A., eds), ASP Conference Series, Vol. 329.Google Scholar
Irwin, J. and Schoichet, B. (2005), ‘ZINC: A free database of commercially available compounds for virtual screening’, J. Chem. Inf. Model. 45, 177–182.Google Scholar
Karcher, H. (1977), ‘Riemannian center of mass and mollifier smoothing’, Comm. Pure Appl. Math. 30, 509–541.Google Scholar
Kendall, W. (1990), ‘Probability, convexity, and harmonic maps with small image I: Uniqueness and fine existence’, Proc. London Math. Soc. 61, 371–406.Google Scholar
Kogan, J. (2007), Introduction to Clustering Large and High-Dimensional Data, Cambridge University Press.Google Scholar
Lee, A., Pedersen, K. and Mumford, D. (2003), ‘The non-linear statistics of high contrast patches in natural images’, Internat. J. Computer Vision 54, 83–103.Google Scholar
Lipsky, D., Skraba, P. and Vejdemo-Johansson, M. (2011), A spectral sequence for parallelized persistence. arXiv:1112.1245Google Scholar
Listing, J. (1848), Vorstudien zur Topologie, Vandenhoeck und Ruprecht.Google Scholar
Lum, P., Singh, G., Carlsson, J., Lehman, A., Ishkhanov, T., Vejdemo-Johansson, M., Alagappan, M. and Carlsson, G. (2013), ‘Extracting insights from the shape of complex data using topology. Nature Scientific Reports 3, # 1236.Google ScholarPubMed
Mac Lane, S. (1998), Categories for the Working Mathematician, second edition, Vol. 5 of Graduate Texts in Mathematics, Springer.Google Scholar
Maleki, A., Shahram, M. and Carlsson, G. (2008), Near optimal coder for image geometries. In Proc. 15th IEEE International Conference on Image Processing (ICIP), pp. 1061–1064.Google Scholar
Mileyko, Y., Mukherjee, S. and Harer, J. (2011), ‘Probability measures on the space of persistence diagrams’, Inverse Problems 27, 1–22.Google Scholar
Milnor, J. (1963), Morse Theory, Princeton University Press.Google Scholar
Munkres, J. (1975), Topology: A First Course, Prentice Hall.Google Scholar
Nicolau, M., Levine, A. and Carlsson, G. (2011), ‘Topology based data analysis identiies a subgroup of breast cancers with a unique mutational proile and excellent survival. Proc. Nat. Acad. Sci. 108, 7265–7270.Google Scholar
Niyogi, P., Smale, S. and Weinberger, S. (2008), ‘Finding the homology of submanifolds with high conidence from random samples’, Discrete Comput. Geom. 39, 419–441.Google Scholar
Park, C., Pranav, P., Chingangram, P., van de Weygaert, R., Jones, B., Vegter, G., Kim, I., Hidding, J. and Helwing, W. (2013), ‘Betti numbers of Gaussian fields’, J. Korean Astron. Soc. 46, 125–131.Google Scholar
Perea, J. and Carlsson, G. (2014), ‘A Klein bottle-based dictionary for texture representation’, Internat. J. Computer Vision 107, 75–97.Google Scholar
Perea, J. and Harer, J. (2014), Sliding windows and persistence: An application of topological methods to signal analysis. arXiv:1307.6188v1Google Scholar
Poincare, H. (1895), ‘Analysis situs’, Journal de l'École Polytechnique (2) 1, 1–123.Google Scholar
Riemann, B. (1851), Grundlagen für eine allgemeine Theorie der Functionen einer veränderlichen complexen Grösse. Dissertation, Göttingen.Google Scholar
Robins, V. (1999), ‘Towards computing homology from finite approximations’, Topology Proceedings 24 (1), 503–532.Google Scholar
Segal, G. (1968), ‘Classifying spaces and spectral sequences’, Inst. Hautes Études Sci. Publ. Math. 34, 105–112.Google Scholar
de Silva, V. and Carlsson, G. (2004), Topological estimation using witness complexes. In Proc. First Eurographics Conference on Point-Based Graphics, pp. 157–166.Google Scholar
Singh, G., Mémoli, F. and Carlsson, G. (2007), Topological methods for the analysis of high dimensional data sets and 3D object recognition. In Proc. Eurographics Symposium on Point-Based Graphics 2007 (Botsch, M. and Pajarola, R., eds).Google Scholar
Sousbie, T. (2011), ‘The persistent cosmic web and its filamentary structure I: Theory and implementation’, Mon. Not. R. Astron. Soc. 414, 350–383.Google Scholar
Sousbie, T., Pichon, C. and Kawahara, H. (2011), ‘The persistent cosmic web and its filamentary structure II: Illustrations’, Mon. Not. R. Astron. Soc. 414, 384–403.Google Scholar
Spergel, D., Bean, R., Dore, O., Nolta, M., Bennett, C., Dunkley, J., Hinshaw, G., Jarosik, N., Komatsu, E., Page, L., Peiris, H., Verde, L., Halpern, M., Hill, R., Kogut, A., Limon, M., Meyer, S. S., Odegards, N., Tucker, G., Weiland, J., Wollack, E. and Wright, E. (2007) ‘Three-year Wilkinson Microwave Anisotropy Probe (WMAP) observations: Implications for cosmology’, As-trophys. J. Supplement Series 170, 377–408.Google Scholar
Turner, K., Mileyko, Y., Mukherjee, S. and Harer, J. (2014), Frechet means for distributions of persistence diagrams. arXiv:1206.2790v2Google Scholar
Vandermonde, A. (1774), Remarques sur les problèmes de situation. In Mémoires de l'Académie Royale des Sciences pour 1771, Paris, pp. 556–574.Google Scholar
van de Weygaert, R., Vegter, G., Edelsbrunner, H., Jones, B., Pranav, P., Park, C., Hellwing, W., Eldering, B., Kruithof, N., Bos, E., Hidding, J., Feldbrugge, J., ten Have, E., van Engelen, M., Caroli, M. and Teillaud, M. (2011), Alpha, Betti, and the Megaparsec Universe: On the topology of the cosmic web. In Transactions on Computational Science XIV (Gavrilova, M.L.et al., eds), Vol. 6970 of Lecture Notes in Computer Science, Springer, pp. 60–101.Google Scholar
Zomorodian, A. (2005), Topology for Computing, Vol. 16 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press.Google Scholar
Zomorodian, A. (2010), The tidy set: A minimal simplicial set for computing homology of clique complexes. In Proc. 2010 Annual Symposium on Computational Geometry, ACM, pp. 257–266.Google Scholar
Zomorodian, A. and Carlsson, G. (2005), ‘Computing persistent homology’, Discrete Comput. Geom. 33, 247–274.Google Scholar