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
Bibliographic Information
- Peter Bürgisser
- Affiliation: Department of Mathematics, University of Paderborn, Germany
- MR Author ID: 316251
- Email: pbuerg@upb.de
- Felipe Cucker
- Affiliation: Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong
- Email: macucker@cityu.edu.hk
- Martin Lotz
- Affiliation: Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong
- Email: lotzm@upb.de
- Received by editor(s): September 28, 2006
- Received by editor(s) in revised form: April 23, 2007
- Published electronically: January 30, 2008
- Additional Notes: Part of these results were announced in C.R. Acad. Sci. Paris, Ser. I 343 (2006) 145–150.
The first author was partially supported by DFG grant BU 1371.
The second and third authors were partially supported by CityU SRG grant 7001860. - © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 1559-1583
- MSC (2000): Primary 65Y20; Secondary 65F35, 65H20
- DOI: https://doi.org/10.1090/S0025-5718-08-02060-7
- MathSciNet review: 2398780