On a condition number of general random polynomial systems

Nguyen, Hoi

doi:10.1090/mcom/2993

On a condition number of general random polynomial systems
HTML articles powered by AMS MathViewer

by Hoi H. Nguyen;

Math. Comp. 85 (2016), 737-757

DOI: https://doi.org/10.1090/mcom/2993

Published electronically: June 24, 2015

PDF | Request permission

Abstract:

Condition numbers of random polynomial systems have been widely studied in the literature under certain coefficient ensembles of invariant type. In this note we introduce a method that allows us to study these numbers for a broad family of probability distributions. Our work also extends to certain perturbed systems.

References

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
Peter Bürgisser and Felipe Cucker, Condition, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 349, Springer, Heidelberg, 2013. The geometry of numerical algorithms. MR 3098452, DOI 10.1007/978-3-642-38896-5
Felipe Cucker, Teresa Krick, Gregorio Malajovich, and Mario Wschebor, A numerical algorithm for zero counting. I. Complexity and accuracy, J. Complexity 24 (2008), no. 5-6, 582–605. MR 2467589, DOI 10.1016/j.jco.2008.03.001
Felipe Cucker, Teresa Krick, Gregorio Malajovich, and Mario Wschebor, A numerical algorithm for zero counting. II. Distance to ill-posedness and smoothed analysis, J. Fixed Point Theory Appl. 6 (2009), no. 2, 285–294. MR 2580979, DOI 10.1007/s11784-009-0127-4
Felipe Cucker, Teresa Krick, Gregorio Malajovich, and Mario Wschebor, A numerical algorithm for zero counting. III: Randomization and condition, Adv. in Appl. Math. 48 (2012), no. 1, 215–248. MR 2845516, DOI 10.1016/j.aam.2011.07.001
Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045
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
Jeff Kahn, János Komlós, and Endre Szemerédi, On the probability that a random $\pm 1$-matrix is singular, J. Amer. Math. Soc. 8 (1995), no. 1, 223–240. MR 1260107, DOI 10.1090/S0894-0347-1995-1260107-2
E. Kostlan, Random polynomials and the statistical fundamental theorem of algebra, unpublished (1987).
Vitali D. Milman and Gideon Schechtman, Asymptotic theory of finite-dimensional normed spaces, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov. MR 856576
Hoi H. Nguyen and Van H. Vu, Small ball probability, inverse theorems, and applications, Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 409–463. MR 3203607, DOI 10.1007/978-3-642-39286-3_{1}6
H. Nguyen, O. Nguyen and V. Vu, On the number of real roots of random polynomials, submitted.
Mark Rudelson, Invertibility of random matrices: norm of the inverse, Ann. of Math. (2) 168 (2008), no. 2, 575–600. MR 2434885, DOI 10.4007/annals.2008.168.575
Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, DOI 10.1016/j.aim.2008.01.010
Mark Rudelson and Roman Vershynin, Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math. 62 (2009), no. 12, 1707–1739. MR 2569075, DOI 10.1002/cpa.20294
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
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 algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463. MR 2145860, DOI 10.1145/990308.990310
Terence Tao and Van H. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. of Math. (2) 169 (2009), no. 2, 595–632. MR 2480613, DOI 10.4007/annals.2009.169.595
Terence Tao and Van Vu, Smooth analysis of the condition number and the least singular value, Math. Comp. 79 (2010), no. 272, 2333–2352. MR 2684367, DOI 10.1090/S0025-5718-2010-02396-8
Terence Tao and Van Vu, Random matrices: the distribution of the smallest singular values, Geom. Funct. Anal. 20 (2010), no. 1, 260–297. MR 2647142, DOI 10.1007/s00039-010-0057-8
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