On the volume of tubular neighborhoods of real algebraic varieties

Lotz, Martin

doi:10.1090/S0002-9939-2014-12397-5

On the volume of tubular neighborhoods of real algebraic varieties
HTML articles powered by AMS MathViewer

by Martin Lotz PDF

Proc. Amer. Math. Soc. 143 (2015), 1875-1889 Request permission

Abstract:

The problem of determining the volume of a tubular neighborhood has a long and rich history. Bounds on the volume of neighborhoods of algebraic sets have turned out to play an important role in the probabilistic analysis of condition numbers in numerical analysis. We present a self-contained derivation of bounds on the probability that a random point, chosen uniformly from a ball, lies within a given distance of a real algebraic variety of any codimension. The bounds are given in terms of the degrees of the defining polynomials, and contain as a special case an unpublished result by Ocneanu.

References

Robert J. Adler and Jonathan E. Taylor, Random fields and geometry, Springer Monographs in Mathematics, Springer, New York, 2007. MR 2319516
Dennis Amelunxen and Peter Bürgisser, Probabilistic analysis of the Grassmann condition number, Foundations of Computational Mathematics , posted on (November 14, 2013), 1–49., DOI 10.1007/s10208-013-9178-4
Dennis Amelunxen, Martin Lotz, Michael B. McCoy, and Joel A. Tropp, Living on the edge: phase transitions in convex programs with random data, Information and Inference , posted on (2014), available at http://imaiai.oxfordjournals.org/content/early/2014/06/28/imaiai.iau005.full.pdf+html., DOI 10.1093/imaiai/iau005
Peter Bürgisser, Smoothed analysis of condition numbers, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2609–2633. MR 2827986
Peter Bürgisser, Felipe Cucker, and Martin Lotz, The probability that a slightly perturbed numerical analysis problem is difficult, Math. Comp. 77 (2008), no. 263, 1559–1583. MR 2398780, DOI 10.1090/S0025-5718-08-02060-7
Peter Bürgisser, Felipe Cucker, and Martin Lotz, Coverage processes on spheres and condition numbers for linear programming, Ann. Probab. 38 (2010), no. 2, 570–604. MR 2642886, DOI 10.1214/09-AOP489
Shiing-shen Chern, On the kinematic formula in integral geometry, J. Math. Mech. 16 (1966), 101–118. MR 0198406, DOI 10.1512/iumj.1967.16.16006
James Weldon Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51 (1987), no. 3, 251–289. MR 895087, DOI 10.1007/BF01400115
James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, DOI 10.1090/S0025-5718-1988-0929546-7
Manfredo Perdigão do Carmo, Riemannian geometry, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the second Portuguese edition by Francis Flaherty. MR 1138207, DOI 10.1007/978-1-4757-2201-7
Herbert Federer, Curvature measures, Trans. Amer. Math. Soc. 93 (1959), 418–491. MR 110078, DOI 10.1090/S0002-9947-1959-0110078-1
Alfred Gray, Tubes, 2nd ed., Progress in Mathematics, vol. 221, Birkhäuser Verlag, Basel, 2004. With a preface by Vicente Miquel. MR 2024928, DOI 10.1007/978-3-0348-7966-8
Misha Gromov and Larry Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates, Duke Math. J. 161 (2012), no. 13, 2549–2603. MR 2988903, DOI 10.1215/00127094-1812840
Ralph Howard, The kinematic formula in Riemannian homogeneous spaces, Mem. Amer. Math. Soc. 106 (1993), no. 509, vi+69. MR 1169230, DOI 10.1090/memo/0509
William Kahan. Conserving Confluence Curbs Ill-Condition. Computer Science Dept., University of California, Berkeley, 1972. Technical Report 6.
Daniel A. Klain and Gian-Carlo Rota, Introduction to geometric probability, Lezioni Lincee. [Lincei Lectures], Cambridge University Press, Cambridge, 1997. MR 1608265
Eric James Kostlan, STATISTICAL COMPLEXITY OF NUMERICAL LINEAR ALGEBRA, ProQuest LLC, Ann Arbor, MI, 1985. Thesis (Ph.D.)–University of California, Berkeley. MR 2634377
Michael B. McCoy and Joel A. Tropp, From Steiner formulas for cones to concentration of intrinsic volumes, Discrete Comput. Geom. 51 (2014), no. 4, 926–963. MR 3216671, DOI 10.1007/s00454-014-9595-4
J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 161339, DOI 10.1090/S0002-9939-1964-0161339-9
John W. Milnor, Topology from the differentiable viewpoint, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Based on notes by David W. Weaver; Revised reprint of the 1965 original. MR 1487640
J. Renegar, On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials, Math. Oper. Res. 12 (1987), no. 1, 121–148. MR 882846, DOI 10.1287/moor.12.1.121
Luis A. Santaló. Integral Geometry and Geometric Probability. Cambridge Mathematical Library. Cambridge University Press, 2004.
Rolf Schneider and Wolfgang Weil, Stochastic and integral geometry, Probability and its Applications (New York), Springer-Verlag, Berlin, 2008. MR 2455326, DOI 10.1007/978-3-540-78859-1
Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1–36. MR 590817, DOI 10.1090/S0273-0979-1981-14858-8
Jakob Steiner, Ueber parallele Flächen, In Karl Weierstrass, editor, Jakob Steiner’s gesammelte Werke, pages 173–176. 1881.
Hermann Weyl, On the Volume of Tubes, Amer. J. Math. 61 (1939), no. 2, 461–472. MR 1507388, DOI 10.2307/2371513
Richard Wongkew, Volumes of tubular neighbourhoods of real algebraic varieties, Pacific J. Math. 159 (1993), no. 1, 177–184. MR 1211391, DOI 10.2140/pjm.1993.159.177