General formulas for the smoothed analysis of condition numbers

Peter Bürgisser; Felipe Cucker; Martin Lotz

doi:10.1016/j.crma.2006.05.014

Numerical Analysis/Differential Geometry

General formulas for the smoothed analysis of condition numbers
[Formules générales pour l'analyse régularisée des nombres de conditionnement]

Présenté par : Philippe G. Ciarlet

Peter Bürgisser ¹ ; Felipe Cucker ² ; Martin Lotz ²

¹ Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
² Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong

Comptes Rendus. Mathématique, Volume 343 (2006) no. 2, pp. 145-150.

Résumé
Abstract

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.

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.

Reçu le : 2006-05-09
Accepté le : 2006-05-16
Publié le : 2006-06-22

DOI : 10.1016/j.crma.2006.05.014

Affiliations des auteurs :

Peter Bürgisser ¹ ; Felipe Cucker ² ; Martin Lotz ²

¹ Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
² Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong

@article{CRMATH_2006__343_2_145_0,
     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},
}

TY  - JOUR
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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2006.05.014/

Bibliographie
Cité par

[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

Cité par Sources :

Commentaires - Politique