Comptes Rendus
Numerical Analysis/Differential Geometry
General formulas for the smoothed analysis of condition numbers
Comptes Rendus. Mathématique, Volume 343 (2006) no. 2, pp. 145-150.

We provide estimates on the volume of tubular neighborhoods around a subvariety Σ of real projective space, intersected with a disk of radius σ. The bounds are in terms of σ, the dimension of the ambient space, and the degree of equations defining Σ. We use these bounds to obtain smoothed analysis estimates for some conic condition numbers.

Nous donnons des estimations du volume de l'intersection des voisinages tubulaires autour d'une sous-variété Σ de l'espace projectif réel avec un disque de rayon σ. Les bornes s'expriment en fonction de σ, de la dimension de l'espace ambiant, et du degré des équations définissant Σ. Nous utilisons ces bornes pour obtenir des estimations au sens de l'analyse régularisé pour des nombres de conditionnement coniques.

Published online:
DOI: 10.1016/j.crma.2006.05.014
Peter Bürgisser 1; Felipe Cucker 2; Martin Lotz 2

1 Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
2 Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong
     author = {Peter B\"urgisser and Felipe Cucker and Martin Lotz},
     title = {General formulas for the smoothed analysis of condition numbers},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {145--150},
     publisher = {Elsevier},
     volume = {343},
     number = {2},
     year = {2006},
     doi = {10.1016/j.crma.2006.05.014},
     language = {en},
AU  - Peter Bürgisser
AU  - Felipe Cucker
AU  - Martin Lotz
TI  - General formulas for the smoothed analysis of condition numbers
JO  - Comptes Rendus. Mathématique
PY  - 2006
SP  - 145
EP  - 150
VL  - 343
IS  - 2
PB  - Elsevier
DO  - 10.1016/j.crma.2006.05.014
LA  - en
ID  - CRMATH_2006__343_2_145_0
ER  - 
%0 Journal Article
%A Peter Bürgisser
%A Felipe Cucker
%A Martin Lotz
%T General formulas for the smoothed analysis of condition numbers
%J Comptes Rendus. Mathématique
%D 2006
%P 145-150
%V 343
%N 2
%I Elsevier
%R 10.1016/j.crma.2006.05.014
%G en
%F CRMATH_2006__343_2_145_0
Peter Bürgisser; Felipe Cucker; Martin Lotz. General formulas for the smoothed analysis of condition numbers. Comptes Rendus. Mathématique, Volume 343 (2006) no. 2, pp. 145-150. doi : 10.1016/j.crma.2006.05.014.

[1] P. Bürgisser, F. Cucker, M. Lotz, Smoothed analysis of complex conic condition numbers, Preprint, 2006

[2] S.-S. Chern On the kinematic formula in integral geometry, J. Math. Mech., Volume 16 (1966), pp. 101-118

[3] J. Demmel The probability that a numerical analysis problem is difficult, Math. Comp., Volume 50 (1988), pp. 449-480

[4] C. Eckart; G. Young The approximation of one matrix by another of lower rank, Psychometrika, Volume 1 (1936), pp. 211-218

[5] A. Gray Tubes, Addison-Wesley Publishing Company Advanced Book Program, Addison-Wesley, Redwood City, CA, 1990

[6] R. Howard The kinematic formula in Riemannian homogeneous spaces, Mem. Amer. Math. Soc., Volume 106 (1993) no. 509, p. vi+69

[7] J. Milnor On the Betti numbers of real varieties, Proc. Amer. Math. Soc., Volume 15 (1964), pp. 275-280

[8] L.A. Santaló Integral Geometry and Geometric Probability, Addison-Wesley Publishing Co., Reading, MA, 1976

[9] D.A. Spielman, S.-H. Teng, Smoothed analysis of algorithms, in: Proceedings of the International Congress of Mathematicians, vol. I, 2002, pp. 597–606

[10] M. Spivak A Comprehensive Introduction to Differential Geometry, vol. III, Publish or Perish Inc., Wilmington, DE, 1979

[11] H. Weyl On the volume of tubes, Amer. J. Math., Volume 61 (1939) no. 2, pp. 461-472

[12] J. Wilkinson Note on matrices with a very ill-conditioned eigenproblem, Numer. Math., Volume 19 (1972), pp. 176-178

Cited by Sources:

Comments - Policy

Articles of potential interest

The complexity to compute the Euler characteristic of complex varieties

Peter Bürgisser; Felipe Cucker; Martin Lotz

C. R. Math (2004)

Average Euler characteristic of random real algebraic varieties

Peter Bürgisser

C. R. Math (2007)