|
Barcodes: The persistent topology of data
Author:
Robert Ghrist
Journal:
Bull. Amer. Math. Soc. 45 (2008), 61-75
MSC (2000):
Primary 55N35; Secondary 62H35
Posted:
October 26, 2007
MathSciNet review:
2358377
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: This article surveys recent work of Carlsson and collaborators on applications of computational algebraic topology to problems of feature detection and shape recognition in high-dimensional data. The primary mathematical tool considered is a homology theory for point-cloud data sets--persistent homology--and a novel representation of this algebraic characterization--barcodes. We sketch an application of these techniques to the classification of natural images.
- 1.
P. Bubenik and P. Kim, ``A statistical approach to persistent homology'', preprint (2006), math.AT/0607634.
- 2.
Erik
Carlsson, Gunnar
Carlsson, and Vin
de Silva, An algebraic topological method for feature
identification, Internat. J. Comput. Geom. Appl. 16
(2006), no. 4, 291–314. MR 2250511
(2007c:52015), http://dx.doi.org/10.1142/S021819590600204X
- 3.
G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian, ``On the local behavior of spaces of natural images'', Intl. J. Computer Vision, in press.
- 4.
G. Carlsson, T. Ishkhanov, F. Mémoli, D. Ringach, and G. Sapiro, ``Topological analysis of the responses of neurons in V1'', in preparation (2007).
- 5.
G. Carlsson, A. Zomorodian, A. Collins, and L. Guibas, ``Persistence barcodes for shapes'', Intl. J. Shape Modeling, 11 (2005), 149-187.
- 6.
F. Chazal and A. Lieutier, ``Weak feature size and persistent homology: computing homology of solids in
 from noisy data samples'', in Proc. 21st Sympos. Comput. Geom. (2005).
- 7.
D. Cohen-Steiner, H. Edelsbrunner, and J. Harer, ``Stability of persistence diagrams'', in Proc. 21st Sympos. Comput. Geom. (2005), 263-271.
- 8.
V. de Silva, ``A weak definition of Delaunay triangulation'', preprint (2003).
- 9.
V. de Silva and G. Carlsson, ``Topological estimation using witness complexes'', in SPBG'04 Symposium on Point-Based Graphics (2004), 157-166.
- 10.
V. de Silva and R. Ghrist, ``Coverage in sensor networks via persistent homology'', Alg. & Geom. Topology, 7 (2007), 339-358.
- 11.
V. de Silva and P. Perry, PLEX home page, http://math.stanford.edu/comptop/programs/plex/.
- 12.
Herbert
Edelsbrunner, David
Letscher, and Afra
Zomorodian, Topological persistence and simplification,
Discrete Comput. Geom. 28 (2002), no. 4,
511–533. Discrete and computational geometry and graph drawing
(Columbia, SC, 2001). MR 1949898
(2003m:52019), http://dx.doi.org/10.1007/s00454-002-2885-2
- 13.
H. Edelsbrunner and E.P. Mücke, ``Three-dimensional alpha shapes'', ACM Transactions on Graphics, 13:1 (1994), 43-72.
- 14.
L. Guibas and S. Oudot, ``Reconstruction using witness complexes'', in Proc. 18th ACM-SIAM Sympos. on Discrete Algorithms (2007).
- 15.
Allen
Hatcher, Algebraic topology, Cambridge University Press,
Cambridge, 2002. MR 1867354
(2002k:55001)
- 16.
Tomasz
Kaczynski, Konstantin
Mischaikow, and Marian
Mrozek, Computational homology, Applied Mathematical Sciences,
vol. 157, Springer-Verlag, New York, 2004. MR 2028588
(2005g:55001)
- 17.
David
Mumford, Pattern theory: the mathematics of perception,
(Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 401–422.
MR
1989195 (2004k:91168)
- 18.
D. Mumford, A. Lee, and K. Pedersen, ``The nonlinear statistics of high-contrast patches in natural images'', Intl. J. Computer Vision, 54 (2003), 83-103.
- 19.
B.
W. Silverman, Density estimation for statistics and data
analysis, Monographs on Statistics and Applied Probability, Chapman
& Hall, London, 1986. MR 848134
(87k:62074)
- 20.
J. van Hateren and A. van der Schaff, ``Independent Component Filters of Natural Images Compared with Simple Cells in Primary Visual Cortex'', Proc. R. Soc. London, B 265 (1998), 359-366.
- 21.
L.
Vietoris, Über den höheren Zusammenhang kompakter
Räume und eine Klasse von zusammenhangstreuen Abbildungen, Math.
Ann. 97 (1927), no. 1, 454–472 (German). MR
1512371, http://dx.doi.org/10.1007/BF01447877
- 22.
Afra
Zomorodian and Gunnar
Carlsson, Computing persistent homology, Discrete Comput.
Geom. 33 (2005), no. 2, 249–274. MR 2121296
(2005j:55004), http://dx.doi.org/10.1007/s00454-004-1146-y
- 23.
A. Zomorodian and G. Carlsson, ``Localized homology'', Proc. Shape Modeling International (2007), 189-198.
- 24.
A. Zomorodian and G. Carlsson, ``The theory of multidimensional persistence'', Proc. Symposium on Computational Geometry (2007), 184-193.
- 1.
- P. Bubenik and P. Kim, ``A statistical approach to persistent homology'', preprint (2006), math.AT/0607634.
- 2.
- E. Carlsson, G. Carlsson, and V. de Silva, ``An algebraic topological method for feature identification'', Intl. J. Computational Geometry and Applications, 16:4 (2006), 291-314. MR 2250511 (2007c:52015)
- 3.
- G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian, ``On the local behavior of spaces of natural images'', Intl. J. Computer Vision, in press.
- 4.
- G. Carlsson, T. Ishkhanov, F. Mémoli, D. Ringach, and G. Sapiro, ``Topological analysis of the responses of neurons in V1'', in preparation (2007).
- 5.
- G. Carlsson, A. Zomorodian, A. Collins, and L. Guibas, ``Persistence barcodes for shapes'', Intl. J. Shape Modeling, 11 (2005), 149-187.
- 6.
- F. Chazal and A. Lieutier, ``Weak feature size and persistent homology: computing homology of solids in from noisy data samples'', in Proc. 21st Sympos. Comput. Geom. (2005).
- 7.
- D. Cohen-Steiner, H. Edelsbrunner, and J. Harer, ``Stability of persistence diagrams'', in Proc. 21st Sympos. Comput. Geom. (2005), 263-271.
- 8.
- V. de Silva, ``A weak definition of Delaunay triangulation'', preprint (2003).
- 9.
- V. de Silva and G. Carlsson, ``Topological estimation using witness complexes'', in SPBG'04 Symposium on Point-Based Graphics (2004), 157-166.
- 10.
- V. de Silva and R. Ghrist, ``Coverage in sensor networks via persistent homology'', Alg. & Geom. Topology, 7 (2007), 339-358.
- 11.
- V. de Silva and P. Perry, PLEX home page, http://math.stanford.edu/comptop/programs/plex/.
- 12.
- H. Edelsbrunner, D. Letscher, and A. Zomorodian, ``Topological persistence and simplification'', Discrete Comput. Geom., 28:4 (2002), 511-533. MR 1949898 (2003m:52019)
- 13.
- H. Edelsbrunner and E.P. Mücke, ``Three-dimensional alpha shapes'', ACM Transactions on Graphics, 13:1 (1994), 43-72.
- 14.
- L. Guibas and S. Oudot, ``Reconstruction using witness complexes'', in Proc. 18th ACM-SIAM Sympos. on Discrete Algorithms (2007).
- 15.
- A. Hatcher, Algebraic Topology, Cambridge University Press (2002). MR 1867354 (2002k:55001)
- 16.
- T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, Applied Mathematical Sciences, 157, Springer-Verlag (2004). MR 2028588 (2005g:55001)
- 17.
- D. Mumford, ``Pattern Theory: The Mathematics of Perception'', Proc. Intl. Congress of Mathematicians, Vol. I (2002), 401-422. MR 1989195 (2004k:91168)
- 18.
- D. Mumford, A. Lee, and K. Pedersen, ``The nonlinear statistics of high-contrast patches in natural images'', Intl. J. Computer Vision, 54 (2003), 83-103.
- 19.
- B. Silverman, Density Estimation for Statistics and Data Analysis, Chapman & Hall/CRC (1986). MR 848134 (87k:62074)
- 20.
- J. van Hateren and A. van der Schaff, ``Independent Component Filters of Natural Images Compared with Simple Cells in Primary Visual Cortex'', Proc. R. Soc. London, B 265 (1998), 359-366.
- 21.
- L. Vietoris, ``Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen'', Math. Ann., 97 (1927), 454-472. MR 1512371
- 22.
- A. Zomorodian and G. Carlsson, ``Computing persistent homology'', Discrete Comput. Geom., 33 (2005), 249-274. MR 2121296 (2005j:55004)
- 23.
- A. Zomorodian and G. Carlsson, ``Localized homology'', Proc. Shape Modeling International (2007), 189-198.
- 24.
- A. Zomorodian and G. Carlsson, ``The theory of multidimensional persistence'', Proc. Symposium on Computational Geometry (2007), 184-193.
Similar Articles
Retrieve articles in Bulletin of the American Mathematical Society
with MSC (2000):
55N35,
62H35
Retrieve articles in all journals
with MSC (2000):
55N35,
62H35
Additional Information
Robert Ghrist
Affiliation:
Department of Mathematics and Coordinated Science Laboratory, University of Illinois, Urbana, Illinois 61801
DOI:
http://dx.doi.org/10.1090/S0273-0979-07-01191-3
PII:
S 0273-0979(07)01191-3
Received by editor(s):
May 16, 2007
Received by editor(s) in revised form:
July 4, 2007
Posted:
October 26, 2007
Additional Notes:
This article is based on the lecture presented at the January 2007 national meeting of the AMS in New Orleans. The author gratefully acknowledges the support of DARPA #HR0011-07-1-0002 and the helpful comments of G. Carlsson, V. de Silva, and A. Zomorodian. The work reviewed in this article is funded by the DARPA program TDA: Topological Data Analysis.
Article copyright:
© Copyright 2007 Robert W. Ghrist
|
