×

The bottleneck degree of algebraic varieties. (English) Zbl 1505.14122

Summary: A bottleneck of a smooth algebraic variety \(X \subset \mathbb{C}^n\) is a pair \((x,y)\) of distinct points \(x,y \in X\) such that the Euclidean normal spaces at \(x\) and \(y\) contain the line spanned by \(x\) and \(y\). The narrowness of bottlenecks is a fundamental complexity measure in the algebraic geometry of data. In this paper we study the number of bottlenecks of affine and projective varieties, which we call the bottleneck degree. The bottleneck degree is a measure of the complexity of computing all bottlenecks of an algebraic variety, using, for example, numerical homotopy methods. We show that the bottleneck degree is a function of classical invariants such as Chern classes and polar classes. We give the formula explicitly in low dimension and provide an algorithm to compute it in the general case.

MSC:

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68Q32 Computational learning theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. Aamari, F. Chazal, J. Kim, B. Michel, A. Rinaldo, and L. Wasserman, Estimating the reach of a manifold, Electron. J. Statist., 13 (2019), pp. 1359-1399. · Zbl 1418.62100
[2] E. Aamari and C. Levrard, Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction, Discrete Comput. Geom., 59 (2018), pp. 923-971. · Zbl 1408.62103
[3] L. Alberti, G. Comte, and B. Mourrain, Meshing implicit algebraic surfaces: The smooth case, in Proceedings of Mathematical Methods for Curves and Surfaces: Tromsø 2004, 2005. · Zbl 1080.65514
[4] E. Arias-Castro, B. Pateiro-López, and A. Rodríguez-Casal, Minimax estimation of the volume of a set under the rolling ball condition, J. Amer. Statist. Assoc., 114 (2019), pp. 1162-1173. · Zbl 1428.62126
[5] S. Balakrishnan, A. Rinaldo, D. Sheehy, A. Singh, and L. Wasserman, Minimax rates for homology inference, in Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, N. D. Lawrence and M. Girolami, eds., Proc. Machine Learn. Res. 22, 2012, pp. 64-72, http://proceedings.mlr.press/v22/balakrishnan12a.html.
[6] B. Bank, M. Giusti, J. Heintz, and G. Mbakop, Polar varieties and efficient real elimination, Math. Z., 238 (2001), pp. 115-144. · Zbl 1073.14554
[7] R. G. Baraniuk and M. B. Wakin, Random projections of smooth manifolds, Found. Comput. Math., 9 (2009), pp. 51-77. · Zbl 1172.53005
[8] D. Bates, J. Hauenstein, A. Sommese, and C. Wampler, Numerically Solving Polynomial Systems with Bertini, Software Environ., Tools 25, SIAM, Philadelphia, 2013. · Zbl 1295.65057
[9] D. J. Bates, W. Decker, J. D. Hauenstein, C. Peterson, G. Pfister, F.-O. Schreyer, A. J. Sommese, and C. W. Wampler, Comparison of probabilistic algorithms for analyzing the components of an affine algebraic variety, Appl. Math. Comput., 231 (2014), pp. 619-633. · Zbl 1410.65205
[10] D. J. Bates, D. Eklund, and C. Peterson, Computing intersection numbers of Chern classes, J. Symbol. Comput., 50 (2013), pp. 493-507, http://www.sciencedirect.com/science/article/pii/S0747717112001587. · Zbl 1263.14005
[11] A. Blum, Random projection, margins, kernels, and feature-selection, in Subspace, Latent Structure and Feature Selection, C. Saunders, M. Grobelnik, S. Gunn, and J. Shawe-Taylor, eds., Springer, Berlin, 2006, pp. 52-68.
[12] J.-D. Boissonnat and A. Ghosh, Triangulating smooth submanifolds with light scaffolding, Math. Comput. Sci., 4 (2011), pp. 431-461. · Zbl 1229.68077
[13] J.-D. Boissonnat and A. Ghosh, Manifold reconstruction using tangential Delaunay complexes, Discrete Comput. Geom., 51 (2014), pp. 221-267. · Zbl 1312.68209
[14] J.-D. Boissonnat and S. Oudot, Provably good sampling and meshing of surfaces, Graphical Models, 67 (2005), pp. 405-451, http://www.sciencedirect.com/science/article/pii/S1524070305000056. · Zbl 1087.68114
[15] M. Brandt and M. Weinstein, Voronoi Cells in Metric Algebraic Geometry of Plane Curves, 2019, https://arxiv.org/abs/arXiv:1906.11337.
[16] P. Breiding, S. Kališnik, B. Sturmfels, and M. Weinstein, Learning algebraic varieties from samples, Rev. Mat. Complut., 31 (2018), pp. 545-593. · Zbl 1481.13040
[17] P. Breiding and S. Timme, The Reach of a Plane Curve, https://www.JuliaHomotopyContinuation.org/examples/reach-curve (2019). · Zbl 1396.14003
[18] P. Breiding and S. Timme, HomotopyContinuation.jl: A Package for Solving Systems of Polynomial Equations in Julia, CoRR, http://arxiv.org/abs/1711.10911, 2017. · Zbl 1396.14003
[19] P. Bürgisser and M. Lotz, The complexity of computing the Hilbert polynomial of smooth equidimensonal complex projective varieties, Found. Comput. Math., 7 (2007), pp. 59-86. · Zbl 1108.68059
[20] K. L. Clarkson, Tighter bounds for random projections of manifolds, in Proceedings of the 24th Annual Symposium on Computational Geometry, ACM, New York, 2008, pp. 39-48. · Zbl 1221.68261
[21] A. Cuevas, R. Fraiman, and A. Rodríguez-Casal, A nonparametric approach to the estimation of lengths and surface areas, Ann. Statist., 35 (2007), pp. 1031-1051. · Zbl 1124.62017
[22] S. Dasgupta and A. Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures Algorithms, 22 (2003), pp. 60-65. · Zbl 1018.51010
[23] S. Di Rocco, D. Eklund, and C. Peterson, Numerical polar calculus and cohomology of line bundles, Adv. Appl. Math., 100 (2017), pp. 148-162. · Zbl 1395.14040
[24] S. Di Rocco, D. Eklund, C. Peterson, and A. J. Sommese, Chern numbers of smooth varieties via homotopy continuation and intersection theory, J. Symbolic Comput., 46 (2011), pp. 23-33. · Zbl 1200.14014
[25] S. Di Rocco, D. Eklund, and M. Weinstein, A Macaulay2 Script to Compute Bottleneck Degree, https://bitbucket.org/daek/bottleneck_script. · Zbl 1505.14122
[26] J. Draisma, E. Horobeb̧t, G. Ottaviani, B. Sturmfels, and R. Thomas, The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16 (2016). · Zbl 1370.51020
[27] E. Dufresne, P. Edwards, H. Harrington, and J. Hauenstein, Sampling Real Algebraic Varieties for Topological Data Analysis, https://arxiv.org/abs/arXiv:1802.07716, 2018.
[28] D. Eisenbud and J. Harris, 3264 and All That: A Second Course in Algebraic Geometry, Cambridge University Press, Cambridge, UK, 2016. · Zbl 1341.14001
[29] D. Eklund, The Numerical Algebraic Geometry of Bottlenecks, https://arxiv.org/abs/arXiv:1804.01015, 2018. · Zbl 1497.14123
[30] D. Eklund, C. Jost, and C. Peterson, A method to compute Segre classes of subschemes of projective space, J. Algebra Appl., 12 (2013). · Zbl 1274.13044
[31] H. Federer, Curvature measures, Trans. Amer. Math. Soci., 93 (1959), pp. 418-491. · Zbl 0089.38402
[32] W. Fulton, Intersection Theory, 2nd ed., Springer, New York, 1998. · Zbl 0885.14002
[33] C. R. Genovese, M. Perone-Pacifico, I. Verdinelli, and L. Wasserman, Minimax manifold estimation, J. Mach. Learn. Res., 13 (2012), pp. 1263-1291. · Zbl 1283.62112
[34] D. R. Grayson and M. E. Stillman, Macaulay2, A Software System for Research in Algebraic Geometry, http://www.math.uiuc.edu/Macaulay2/.
[35] D. R. Grayson, M. E. Stillman, S. A. Strømme, D. Eisenbud, and C. Crissman, Schubert2: Computations of Characteristic Classes for Varieties Without Equations, Version 0.7, https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages.
[36] J. Harris, Algebraic Geometry, Springer, New York, 1992. · Zbl 0932.14001
[37] C. Hegde, M. Wakin, and R. Baraniuk, Random projections for manifold learning, in Advances in Neural Information Processing Systems 20, J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, eds., Curran Associates, Red Hook, NY, 2008, pp. 641-648, http://papers.nips.cc/paper/3191-random-projections-for-manifold-learning.pdf.
[38] E. Horobeb̧t and M. Weinstein, Offset hypersurfaces and persistent homology of algebraic varieties, Comput. Aided Geom. Design, 74 (2018).
[39] Mathematica, Version 12.0, Wolfram, Champaign, IL, 2019.
[40] K. W. Johnson, Immersion and embedding of projective varieties, Acta Math., 140 (1978), pp. 49-74. · Zbl 0373.14005
[41] A. K. H. Kim and H. H. Zhou, Tight minimax rates for manifold estimation under Hausdorff loss, Electron. J. Stat., (2015), pp. 1562-1582. · Zbl 1325.62111
[42] S. Kleiman, Tangency and duality, in Proceedings of the 1984 Vancouver Conference in Algebraic Geometry, Vol. 6, 1986, pp. 163-225. · Zbl 0601.14046
[43] Z. Kukelova, M. Byröd, K. Josephson, T. Pajdla, and K. \AAström, Fast and robust numerical solutions to minimal problems for cameras with radial distortion, Comput. Vision Image Understanding, 114 (2010), pp. 234-244.
[44] D. Laksov, Residual intersections and Todd’s formula for the double locus of a morphism, Acta Math., 140 (1978), pp. 75-92. · Zbl 0388.14006
[45] J. B. Lasserre, An Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge Texts Appl. Math., Cambridge University Press, Cambridge, UK, 2015. · Zbl 1320.90003
[46] R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Econom. Theory, 72 (1997), pp. 411-425, http://www.sciencedirect.com/science/article/pii/S0022053196922140. · Zbl 0883.90130
[47] D. Mehta, T. Chen, T. Tang, and J. D. Hauenstein, The Loss Surface of Deep Linear Networks Viewed Through the Algebraic Geometry Lens, https://arxiv.org/abs/arXiv:1810.07716, 2018.
[48] M. Minimair and M. P. Barnett, Solving polynomial equations for chemical problems using Gröbner bases, Molecular Phys., 102 (2004), pp. 2521-2535.
[49] P. Niyogi, S. Smale, and S. Weinberger, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39 (2008), pp. 419-441. · Zbl 1148.68048
[50] R. Piene, Polar classes of singular varieties, Ann. Sci. Éc. Norm. Supér. (4), 11 (1978), pp. 247-276. · Zbl 0401.14007
[51] R. Piene, Polar varieties revisited, in Computer Algebra and Polynomials, Lecture Notes in Comput. Sci. 8942, Springer, New York, 2015, pp. 139-150. · Zbl 1439.14141
[52] M. Safey El Din and P.-J. Spaenlehauer, Critical point computations on smooth varieties: Degree and complexity bounds, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2016, pp. 183-190. · Zbl 1362.14061
[53] A. J. Sommese and C. W. Wampler, The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, World Scientific, Singapore, 2005. · Zbl 1091.65049
[54] B. Sturmfels, Solving Systems of Polynomial Equations, CBMS Reg. Conf. Ser. 97, AMS, Providence, RI, 2002. · Zbl 1101.13040
[55] N. Verma, A Note on Random Projections for Preserving Paths on a Manifold, Tech. report CS2011-0971, UC San Diego, 2011.
[56] C. W. Wampler and A. J. Sommese, Numerical algebraic geometry and algebraic kinematics, Acta Numer., 20 (2011), pp. 469-567. · Zbl 1254.13031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.