The probability that a slightly perturbed numerical analysis problem is difficult

Bürgisser, Peter; Cucker, Felipe; Lotz, Martin

doi:10.1090/S0025-5718-08-02060-7

The probability that a slightly perturbed numerical analysis problem is difficult
HTML articles powered by AMS MathViewer

by Peter Bürgisser, Felipe Cucker and Martin Lotz;

Math. Comp. 77 (2008), 1559-1583

DOI: https://doi.org/10.1090/S0025-5718-08-02060-7

Published electronically: January 30, 2008

PDF | Request permission

Abstract:

We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of $\varepsilon$-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius $\sigma$. Besides $\varepsilon$ and $\sigma$, this bound depends only on the dimension of the sphere and on the degree of the defining equations.

References

C. Beltrán and L. M. Pardo, Estimates on the distribution of the condition number of singular matrices, Found. Comput. Math. 7 (2007), no. 1, 87–134. MR 2283343, DOI 10.1007/s10208-005-0176-2
Adi Ben-Israel and Thomas N. E. Greville, Generalized inverses, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 15, Springer-Verlag, New York, 2003. Theory and applications. MR 1987382
Lenore Blum, Lectures on a theory of computation and complexity over the reals (or an arbitrary ring), 1989 lectures in complex systems (Santa Fe, NM, 1989) Santa Fe Inst. Stud. Sci. Complexity Lectures, II, Addison-Wesley, Redwood City, CA, 1990, pp. 1–47. MR 1104440
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509, DOI 10.1007/978-3-662-03718-8
Peter Bürgisser, Felipe Cucker, and Martin Lotz, General formulas for the smoothed analysis of condition numbers, C. R. Math. Acad. Sci. Paris 343 (2006), no. 2, 145–150 (English, with English and French summaries). MR 2243310, DOI 10.1016/j.crma.2006.05.014
Peter Bürgisser, Felipe Cucker, and Martin Lotz, Smoothed analysis of complex conic condition numbers, J. Math. Pures Appl. (9) 86 (2006), no. 4, 293–309 (English, with English and French summaries). MR 2257845, DOI 10.1016/j.matpur.2006.06.001
S.L. Campbell and C.D. Meyer. Generalized Inverse of Linear Transformations. Pitman, 1979.
Shiing-shen Chern, On the kinematic formula in integral geometry, J. Math. Mech. 16 (1966), 101–118. MR 198406, DOI 10.1512/iumj.1967.16.16006
Dennis Cheung and Felipe Cucker, A note on level-2 condition numbers, J. Complexity 21 (2005), no. 3, 314–319. MR 2138441, DOI 10.1016/j.jco.2004.06.004
F. Cucker, H. Diao, and Y. Wei, Smoothed analysis of some condition numbers, Numer. Linear Algebra Appl. 13 (2006), no. 1, 71–84. MR 2194973, DOI 10.1002/nla.464
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
J. Dunagan, D.A. Spielman, and S.-H. Teng. Smoothed analysis of Renegar’s condition number for linear programming. Preprint available at http://theory.lcs.mit.edu/~spielman, 2003.
C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1:211–218, 1936.
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Alfred Gray, Tubes, Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1990. MR 1044996
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
E. Kostlan, On the distribution of roots of random polynomials, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) Springer, New York, 1993, pp. 419–431. MR 1246137
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
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, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 433364
I. R. Shafarevich, Basic algebraic geometry, Die Grundlehren der mathematischen Wissenschaften, Band 213, Springer-Verlag, New York-Heidelberg, 1974. Translated from the Russian by K. A. Hirsch. MR 366917
Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4
M. Shub and S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR 1230872, DOI 10.1007/978-1-4612-2752-6_{1}9
Michael Shub and Steve Smale, Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR 1213484, DOI 10.1006/jcom.1993.1002
M. Shub and S. Smale, Complexity of Bezout’s theorem. V. Polynomial time, Theoret. Comput. Sci. 133 (1994), no. 1, 141–164. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294430, DOI 10.1016/0304-3975(94)90122-8
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
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
Steve Smale, Complexity theory and numerical analysis, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 523–551. MR 1489262, DOI 10.1017/S0962492900002774
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 597–606. MR 1989210
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of termination of linear programming algorithms, Math. Program. 97 (2003), no. 1-2, Ser. B, 375–404. ISMP, 2003 (Copenhagen). MR 2004403, DOI 10.1007/s10107-003-0448-9
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463. MR 2145860, DOI 10.1145/990308.990310
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms and heuristics: progress and open questions, Foundations of computational mathematics, Santander 2005, London Math. Soc. Lecture Note Ser., vol. 331, Cambridge Univ. Press, Cambridge, 2006, pp. 274–342. MR 2277110, DOI 10.1017/CBO9780511721571.010
M. Spivak. A comprehensive introduction to differential geometry. Vol. I. Publish or Perish Inc., Wilmington, Del., second edition, 1979.
M. Spivak. A comprehensive introduction to differential geometry. Vol. III. Publish or Perish Inc., Wilmington, Del., second edition, 1979.
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
R. Sulanke and P. Wintgen, Differentialgeometrie und Faserbündel, Lehrbücher und Monographien aus dem Gebiete der Exakten Wissenschaften, Mathematische Reihe, Band 48, Birkhäuser Verlag, Basel-Stuttgart, 1972 (German). MR 413153
John A. Thorpe, Elementary topics in differential geometry, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1994. Corrected reprint of the 1979 original. MR 1329997
A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287–308. MR 28100, DOI 10.1093/qjmam/1.1.287
John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 24235, DOI 10.1090/S0002-9904-1947-08909-6
Hermann Weyl, On the Volume of Tubes, Amer. J. Math. 61 (1939), no. 2, 461–472. MR 1507388, DOI 10.2307/2371513
H. Weyl. The Theory of Groups and Quantum Mechanics. Dover, New York, 1950.
J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 311092, DOI 10.1007/BF01402528
Richard Wongkew, Volumes of tubular neighbourhoods of real algebraic varieties, Pacific J. Math. 159 (1993), no. 1, 177–184. MR 1211391
Mario Wschebor, Smoothed analysis of $\kappa (A)$, J. Complexity 20 (2004), no. 1, 97–107. MR 2031560, DOI 10.1016/j.jco.2003.09.003

AMS Website Down

Mathematics of Computation

The probability that a slightly perturbed numerical analysis problem is difficult
HTML articles powered by AMS MathViewer

Abstract: