Sampling and homology via bottlenecks
HTML articles powered by AMS MathViewer
- by Sandra Di Rocco, David Eklund and Oliver Gäfvert HTML | PDF
- Math. Comp. 91 (2022), 2969-2995 Request permission
Abstract:
In this paper we present an efficient algorithm to produce a provably dense sample of a smooth compact affine variety. The procedure is partly based on computing bottlenecks of the variety. Using geometric information such as the bottlenecks and the local reach we also provide bounds on the density of the sample needed in order to guarantee that the homology of the variety can be recovered from the sample. An implementation of the algorithm is provided together with numerical experiments and a computational comparison to the algorithm by Dufresne et al. [Sampling real algebraic varieties for topological data analysis, arXiv:1802.07716, 2018].References
- Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman, Estimating the reach of a manifold, Electron. J. Stat. 13 (2019), no. 1, 1359–1399. MR 3938326, DOI 10.1214/19-ejs1551
- D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, Bertini: Software for numerical algebraic geometry, dx.doi.org/10.7274/R0H41PB5, 2018.
- Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Numerically solving polynomial systems with Bertini, Software, Environments, and Tools, vol. 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3155500
- P. Breiding, F. Sottile, and J. Woodcock, Euclidean distance degree and mixed volume, Found. Comput. Math., 2021.
- Paul Breiding and Orlando Marigliano, Random points on an algebraic manifold, SIAM J. Math. Data Sci. 2 (2020), no. 3, 683–704. MR 4138210, DOI 10.1137/19M1271178
- P. Breiding and S. Timme, The reach of a plane curve, https://www.JuliaHomotopyContinuation.org/examples/reach-curve/. Accessed: November 5, 2019.
- P. Breiding and S. Timme, HomotopyContinuation.jl: A package for homotopy continuation in Julia, In International Congress on Mathematical Software, Springer, 2018, pp. 458–465.
- Peter Bürgisser, Felipe Cucker, and Pierre Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2019), no. 1, Art. 5, 30. [Publication date initially given as 2018]. MR 3892564, DOI 10.1145/3275242
- Peter Bürgisser, Felipe Cucker, and Josué Tonelli-Cueto, Computing the homology of semialgebraic sets. I: Lax formulas, Found. Comput. Math. 20 (2020), no. 1, 71–118. MR 4056926, DOI 10.1007/s10208-019-09418-y
- Peter Bürgisser, Felipe Cucker, and Josué Tonelli-Cueto, Computing the homology of semialgebraic sets. II: General formulas, Found. Comput. Math. 21 (2021), no. 5, 1279–1316. MR 4323618, DOI 10.1007/s10208-020-09483-8
- Frédéric Chazal, David Cohen-Steiner, and André Lieutier, A sampling theorem for compact sets in Euclidean space, Discrete Comput. Geom. 41 (2009), no. 3, 461–479. MR 2486371, DOI 10.1007/s00454-009-9144-8
- Frédéric Chazal and André Lieutier, Weak feature size and persistant homology: computing homology of solids in $\Bbb R^n$ from noisy data samples, Computational geometry (SCG’05), ACM, New York, 2005, pp. 255–262. MR 2460371, DOI 10.1145/1064092.1064132
- F. Chazal and A. Lieutier, The “$\lambda$-medial axis”, Graph. Models, 67 (2005), no. 4, 304–331.
- Mahdi Cheraghchi and Amin Shokrollahi, Almost-uniform sampling of points on high-dimensional algebraic varieties, STACS 2009: 26th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 3, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2009, pp. 277–288. MR 2870659
- E. A. Coutsias, S. Martin, J. P. Thompson, and A. Watson, Topology of cyclo-octane energy landscape, J. Chem Phys., 132 (2010), 234115.
- Felipe Cucker, Teresa Krick, and Michael Shub, Computing the homology of real projective sets, Found. Comput. Math. 18 (2018), no. 4, 929–970. MR 3833646, DOI 10.1007/s10208-017-9358-8
- Sandra Di Rocco, David Eklund, Andrew J. Sommese, and Charles W. Wampler, Algebraic $\Bbb C^*$-actions and the inverse kinematics of a general 6R manipulator, Appl. Math. Comput. 216 (2010), no. 9, 2512–2524. MR 2653064, DOI 10.1016/j.amc.2009.12.014
- Sandra Di Rocco, David Eklund, and Madeleine Weinstein, The bottleneck degree of algebraic varieties, SIAM J. Appl. Algebra Geom. 4 (2020), no. 1, 227–253. MR 4078795, DOI 10.1137/19M1265776
- Persi Diaconis, Susan Holmes, and Mehrdad Shahshahani, Sampling from a manifold, Advances in modern statistical theory and applications: a Festschrift in honor of Morris L. Eaton, Inst. Math. Stat. (IMS) Collect., vol. 10, Inst. Math. Statist., Beachwood, OH, 2013, pp. 102–125. MR 3586941
- E. Dufresne, P. B. Edwards, H. A. Harrington, and J. D. Hauenstein, Sampling real algebraic varieties for topological data analysis, arXiv:1802.07716, 2018.
- P. Edwards, Package for sampling real algebraic varieties, https://github.com/P-Edwards/tdasampling. Accessed: January 7, 2020.
- D. Eklund, The numerical algebraic geometry of bottlenecks, arXiv:1804.01015, 2018.
- Herbert Federer, Curvature measures, Trans. Amer. Math. Soc. 93 (1959), 418–491. MR 110078, DOI 10.1090/S0002-9947-1959-0110078-1
- O. Gäfvert, Sampling and homology via bottlenecks, https://www.JuliaHomotopyContinuation.org/examples/sampling_bottlenecks/. Accessed: October 13, 2020.
- Joe Harris, Algebraic geometry, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1992. A first course. MR 1182558, DOI 10.1007/978-1-4757-2189-8
- Jonathan D. Hauenstein, Numerically computing real points on algebraic sets, Acta Appl. Math. 125 (2013), 105–119. MR 3048642, DOI 10.1007/s10440-012-9782-3
- Emil Horobeţ and Madeleine Weinstein, Offset hypersurfaces and persistent homology of algebraic varieties, Comput. Aided Geom. Design 74 (2019), 101767, 14. MR 3996403, DOI 10.1016/j.cagd.2019.101767
- J. D. Hunter, Matplotlib: A 2d graphics environment, Comput. Sci. Eng., 9 (2007), no. 3, 90–95.
- Wolfram Research, Inc., Mathematica, Version 12.0, Champaign, IL, 2019.
- Steven L. Kleiman and John Landolfi, Geometry and deformation of special Schubert varieties, Compositio Math. 23 (1971), 407–434. MR 314855
- John M. Lee, Introduction to smooth manifolds, 2nd ed., Graduate Texts in Mathematics, vol. 218, Springer, New York, 2013. MR 2954043
- W. E. Lorensen and H. E. Cline, Marching cubes: A high resolution 3d surface construction algorithm, In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’87, New York, NY, USA, 1987, pp. 163–169. Association for Computing Machinery.
- Partha Niyogi, Stephen Smale, and Shmuel Weinberger, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom. 39 (2008), no. 1-3, 419–441. MR 2383768, DOI 10.1007/s00454-008-9053-2
- Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Second expanded edition, Encyclopedia of Mathematics and its Applications, vol. 151, Cambridge University Press, Cambridge, 2014. MR 3155183
- A. Seidenberg, A new decision method for elementary algebra, Ann. of Math. (2) 60 (1954), 365–374. MR 63994, DOI 10.2307/1969640
- J. M. Selig, Geometric fundamentals of robotics, 2nd ed., Monographs in Computer Science, Springer, New York, 2005. MR 2250553
- Michael Shub and Steve Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128–148. MR 1377247, DOI 10.1137/0733008
- Andrew J. Sommese and Charles W. Wampler II, The numerical solution of systems of polynomials, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. Arising in engineering and science. MR 2160078, DOI 10.1142/9789812567727
Additional Information
- Sandra Di Rocco
- Affiliation: Department of mathematics, KTH, 10044 Stockholm, Sweden
- MR Author ID: 606949
- ORCID: 0000-0002-7186-1524
- Email: dirocco@math.kth.se
- David Eklund
- Affiliation: RISE, Research Institutes of Sweden, Isafjordsgatan 22, 16440 Kista, Sweden
- MR Author ID: 906385
- Email: daek@math.kth.se
- Oliver Gäfvert
- Affiliation: Mathematical Institute, University of Oxford, United Kingdom
- Email: oliver.gafvert@maths.ox.ac.uk
- Received by editor(s): November 2, 2020
- Received by editor(s) in revised form: October 13, 2021, and April 12, 2022
- Published electronically: July 22, 2022
- Additional Notes: The third author was supported by the Thematic Einstein Semester ”Varieties, Polyhedra, Computation” by the Berlin Einstein Foundation. All three authors were supported by Vetenstapsrådet grants [NT:2014-4763], [NT:2018-03688]
- © Copyright 2022 American Mathematical Society
- Journal: Math. Comp. 91 (2022), 2969-2995
- MSC (2020): Primary 13P25, 14Q20, 14P25
- DOI: https://doi.org/10.1090/mcom/3757
- MathSciNet review: 4473110