The theory of multidimensional persistence

ABSTRACT

Persistent homology captures the topology of a filtration - a one-parameter family of increasing spaces - in terms of a complete discrete invariant. This invariant is a multiset of intervals that denote the lifetimes of the topological entities within the filtration. In many applications of topology, we need to study a multifiltration: a family of spaces parameterized along multiple geometric dimensions. In this paper, we show that no similar complete discrete invariant exists for multidimensional persistence. Instead, we propose the rank invariant, a discrete invariant for the robust estimation of Betti numbers in a multifiltration, and prove its completeness in one dimension.

REFERENCES

• 1: [1] Carlsson, G., Zomorodian, A., Collins, A., and Guibas, L. J. Persistence barcodes for shapes. International Journal of Shape Modeling 11, 2 (2005), 149-187.
• 2: Frédéric Chazal , André Lieutier, Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064132]
• 3: [3] COHEN, D. C., AND ORLIK, P. Gauss-Manin connections for arrangements I. Eigenvalues. Compositio Math. 136, 3 (2003), 299-316.
• 4: [4] COLLINS, A., ZOMORODIAN, A., CARLSSON, G., AND GUIBAS, L. A barcode shape descriptor for curve point cloud data. Computers and Graphics 28 (2004), 881-894.
• 5: [5] DE SILVA, V., AND CARLSSON, G. Topological estimation using witness complexes. In Proceedings of the Symposium on Point-Based Graphics (2004), pp. 157-166.
• 6: [6] DE SILVA, V., GHRIST, R., AND MUHAMMAD, A. Blind swarms for coverage in 2-D. In Proceedings of Robotics: Science and Systems (2005).
• 7: [7] EDELSBRUNNER, H., LETSCHER, D., AND ZOMORODIAN, A. Topological persistence and simplification. Discrete and Computational Geometry 28 (2002), 511-533.
• 8: [8] EISENBUD, D. Commutative algebra with a view toward algebraic geometry, vol. 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.
• 9: [9] EISENBUD, D. The geometry of syzygies: A second course in commutative algebra and algebraic geometry, vol. 229 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2005.
• 10: [10] FROSINI, P., AND MULAZZANI, M. Size homotopy groups for computation of natural size distances. Bull. Belg. Math. Soc. Simon Stevin 6, 3 (1999), 455-464.
• 11: [11] GABRIEL, P., AND ROITER, A. V. Representations of Finite-Dimensional Algebras. Springer-Verlag, Berlin, 1997.
• 12: [12] GROMOV, M. Hyperbolic groups. In Essays in Group Theory, S. Gersten, Ed. Springer Verlag, New York, NY, 1987, pp. 75-263.
• 13: [13] GYULASSY, A., NATARAJAN, V., PASCUCCI, V., BREMER, P. T., AND HAMANN, B. Topology-based simplification for feature extraction from 3D scalar fields. In Proceedings of IEEE Visualization (2005), pp. 275-280.
• 14: [14] MUMFORD, D., FOGARTY, J., AND KIRWAN, F. Geometric Invariant Theory, third ed., vol. 34 of Ergebnisse der Mathematik und ihrer Grenzgebiete (2). Springer-Verlag, Berlin, 1994.
• 15: [15] TERAO, H. Moduli space of combinatorially equivalent arrangements of hyperplanes and logarithmic Gauss-Manin connections. Topology Appl. 118, 1-2 (2002), 255-274.
• 16: [16] WEIBEL, C. A. An Introduction to Homological Algebra, vol. 38 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1994.
• 17: Afra Zomorodian , Gunnar Carlsson, Computing Persistent Homology, Discrete & Computational Geometry, v.33 n.2, p.249-274, February 2005 [doi>10.1007/s00454-004-1146-y]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
computational topology, multidimensional analysis, persistent homology