Document Open Access Logo

Polynomial-Sized Topological Approximations Using the Permutahedron

Authors Aruni Choudhary, Michael Kerber, Sharath Raghvendra

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2016.31.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • Persistent Homology
  • Topological Data Analysis
  • Simplicial Approximation
  • Permutahedron
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in R^d, we obtain a O(d)-approximation with at most n2^{O(d log k)} simplices of dimension k or lower. In conjunction with dimension reduction techniques, our approach yields a O(polylog (n))-approximation of size n^{O(1)} for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. 

Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every (1+epsilon)-approximation of the Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n) for c in (0,1).

Cite As Get BibTex

Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Polynomial-Sized Topological Approximations Using the Permutahedron. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.31

Author Details

Aruni Choudhary
Michael Kerber
Sharath Raghvendra

References

  1. J. Baek and A.Adams. Some useful properties of the Permutohedral Lattice for Gaussian filtering. Technical report, Stanford University, 2009. URL: http://graphics.stanford.edu/papers/permutohedral/permutohedral_techreport.pdf.
  2. R. Bambah. On Lattice coverings by Spheres. Proceedings of the National Institute of Sciences of India, 20:25-52, 1954. Google Scholar
  3. K. Borsuk. On the embedding of systems of Compacta in Simplicial Complexes. Fundamenta Mathematicae, pages 217-234, 1948. Google Scholar
  4. M. Botnan and G. Spreemann. Approximating Persistent Homology in Euclidean space through collapses. Applied Algebra in Engineering, Communication and Computing, 26(1-2):73-101, 2015. URL: http://dx.doi.org/10.1007/s00200-014-0247-y.
  5. J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics, 52(1-2):46-52, 1985. URL: http://dx.doi.org/10.1007/BF02776078.
  6. P. Bubenik and J.A. Scott. Categorification of Persistent Homology. Discrete &Computational Geometry, 51(3):600-627, 2014. URL: http://dx.doi.org/10.1007/s00454-014-9573-x.
  7. F. Chazal, D. Cohen-Steiner, M. Glisse, L.J. Guibas, and S.Y. Oudot. Proximity of Persistence Modules and their Diagrams. In ACM Symposium on Computational Geometry (SoCG), pages 237-246, 2009. URL: http://dx.doi.org/10.1145/1542362.1542407.
  8. A. Choudhary, M. Kerber, and S. Raghvendra. Polynomial-sized Topological Approximations using the Permutahedron. CoRR, abs/1601.02732, 2016. URL: http://arxiv.org/abs/1601.02732.
  9. A. Choudhary, M. Kerber, and R. Sharathkumar. Approximate Čech complexes in low and high dimensions. URL: http://people.mpi-inf.mpg.de/~achoudha/Files/AppCech.pdf.
  10. J. H. Conway, N. J. A. Sloane, and E. Bannai. Sphere-packings, Lattices, and Groups. Springer-Verlag, 1987. Google Scholar
  11. T.K. Dey, F. Fan, and Y. Wang. Computing topological persistence for simplicial maps. In ACM Symposium on Computational Geometry (SoCG), pages 345-354, 2014. URL: http://dx.doi.org/10.1145/2582112.2582165.
  12. H. Edelsbrunner and J. Harer. Computational Topology - an Introduction. American Mathematical Society, 2010. URL: http://www.ams.org/bookstore-getitem/item=MBK-69.
  13. H. Edelsbrunner and E.P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 1990. URL: http://dx.doi.org/10.1145/77635.77639.
  14. T. Hales. A proof of the Kepler conjecture. Annals of Mathematics, 162:1065-1185, 2005. Google Scholar
  15. A. Hatcher. Algebraic Topology. Cambridge Univ. Press, 2001. Google Scholar
  16. W.B. Johnson, J. Lindenstrauss, and G. Schechtman. Extensions of Lipschitz maps into Banach spaces. Israel Journal of Mathematics, 54(2):129-138, 1986. URL: http://dx.doi.org/10.1007/BF02764938.
  17. H. Jung. Über die kleinste Kugel, die eine räumliche Figur einschliesst. Journal reine angewandte Mathematik, 123:241-257, 1901. Google Scholar
  18. M. Kerber and S. Raghvendra. Approximation and streaming algorithms for projective clustering via random projections. In Canadian Conference on Computational Geometry (CCCG), pages 179-185, 2015. Google Scholar
  19. M. Kerber and R. Sharathkumar. Approximate Čech complex in low and high dimensions. In Intern. Symp. on Algortihms and Computation (ISAAC), pages 666-676, 2013. Google Scholar
  20. J. Matoušek. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Commentationes Mathematicae Universitatis Carolinae, 1990. Google Scholar
  21. J.R. Munkres. Elements of algebraic topology. Westview Press, 1984. Google Scholar
  22. B.C. Rennie and A.J. Dobson. On Stirling numbers of the second kind. Journal of Combinatorial Theory, 7(2):116-121, 1969. Google Scholar
  23. D. Sheehy. Linear-size approximations to the Vietoris-Rips Filtration. Discrete & Computational Geometry, 49(4):778-796, 2013. URL: http://dx.doi.org/10.1007/s00454-013-9513-1.
  24. D. Sheehy. The persistent homology of distance functions under random projection. In ACM Symposium on Computational Geometry (SoCG), 2014. Google Scholar
  25. G.M. Ziegler. Lectures on polytopes. Springer-Verlag, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact