Smoothed analysis for the condition number of structured real polynomial systems

Ergür, Alperen; Paouris, Grigoris; Rojas, J.

doi:10.1090/mcom/3647

Smoothed analysis for the condition number of structured real polynomial systems
HTML articles powered by AMS MathViewer

by Alperen A. Ergür, Grigoris Paouris and J. Maurice Rojas;

Math. Comp. 90 (2021), 2161-2184

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

Published electronically: June 18, 2021

HTML | PDF | Request permission

Abstract:

We consider the sensitivity of real zeros of structured polynomial systems to pertubations of their coefficients. In particular, we provide explicit estimates for condition numbers of structured random real polynomial systems and extend these estimates to the smoothed analysis setting.

References

Carlos Beltrán and Luis Miguel Pardo, Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J. Amer. Math. Soc. 22 (2009), no. 2, 363–385. MR 2476778, DOI 10.1090/S0894-0347-08-00630-9
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
Peter Bürgisser, Felipe Cucker, and Pierre Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2019), no. 1, Art. 5, 30. [Publication date initially given as 2018]. MR 3892564, DOI 10.1145/3275242
Peter Bürgisser, Felipe Cucker, and Josué Tonelli-Cueto, Computing the homology of semialgebraic sets. I: Lax formulas, Found. Comput. Math. 20 (2020), no. 1, 71–118. MR 4056926, DOI 10.1007/s10208-019-09418-y
Felipe Cucker, Approximate zeros and condition numbers, J. Complexity 15 (1999), no. 2, 214–226. MR 1693884, DOI 10.1006/jcom.1999.0503
Felipe Cucker, Alperen A. Ergür, and Josue Tonelli-Cueto, Plantinga-Vegter algorithm takes average polynomial time, ISSAC’19—Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2019, pp. 114–121. MR 4007450
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
Felipe Cucker, Teresa Krick, and Michael Shub, Computing the homology of real projective sets, Found. Comput. Math. 18 (2018), no. 4, 929–970. MR 3833646, DOI 10.1007/s10208-017-9358-8
Sjoerd Dirksen, Tail bounds via generic chaining, Electron. J. Probab. 20 (2015), no. 53, 29. MR 3354613, DOI 10.1214/EJP.v20-3760
Alperen A. Ergür, Grigoris Paouris, and J. Maurice Rojas, Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions, Found. Comput. Math. 19 (2019), no. 1, 131–157. MR 3913875, DOI 10.1007/s10208-018-9380-5
Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363, DOI 10.1080/01621459.1963.10500830
O. D. Kellogg, On bounded polynomials in several variables, Math. Z. 27 (1928), no. 1, 55–64. MR 1544896, DOI 10.1007/BF01171085
B. Klartag and S. Mendelson, Empirical processes and random projections, J. Funct. Anal. 225 (2005), no. 1, 229–245. MR 2149924, DOI 10.1016/j.jfa.2004.10.009
Pierre Lairez, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Found. Comput. Math. 17 (2017), no. 5, 1265–1292. MR 3709332, DOI 10.1007/s10208-016-9319-7
Christopher Liaw, Abbas Mehrabian, Yaniv Plan, and Roman Vershynin, A simple tool for bounding the deviation of random matrices on geometric sets, Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2169, Springer, Cham, 2017, pp. 277–299. MR 3645128
Galyna Livshyts, Grigoris Paouris, and Peter Pivovarov, On sharp bounds for marginal densities of product measures, Israel J. Math. 216 (2016), no. 2, 877–889. MR 3557469, DOI 10.1007/s11856-016-1431-5
Hoi H. Nguyen, On a condition number of general random polynomial systems, Math. Comp. 85 (2016), no. 298, 737–757. MR 3434879, DOI 10.1090/mcom/2993
Grigoris Paouris and Peter Pivovarov, Randomized isoperimetric inequalities, Convexity and concentration, IMA Vol. Math. Appl., vol. 161, Springer, New York, 2017, pp. 391–425. MR 3837278
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
Mark Rudelson and Roman Vershynin, Small ball probabilities for linear images of high-dimensional distributions, Int. Math. Res. Not. IMRN 19 (2015), 9594–9617. MR 3431603, DOI 10.1093/imrn/rnu243
Gideon Schechtman, Two observations regarding embedding subsets of Euclidean spaces in normed spaces, Adv. Math. 200 (2006), no. 1, 125–135. MR 2199631, DOI 10.1016/j.aim.2004.11.003
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
Steve Smale, Mathematical problems for the next century, Math. Intelligencer 20 (1998), no. 2, 7–15. MR 1631413, DOI 10.1007/BF03025291
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
Michel Talagrand, The generic chaining, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2005. Upper and lower bounds of stochastic processes. MR 2133757
Roman Vershynin, High-dimensional probability, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, 2018. An introduction with applications in data science; With a foreword by Sara van de Geer. MR 3837109, DOI 10.1017/9781108231596
Roman Vershynin, Four lectures on probabilistic methods for data science, The mathematics of data, IAS/Park City Math. Ser., vol. 25, Amer. Math. Soc., Providence, RI, 2018, pp. 231–271. MR 3839170, DOI 10.1090/pcms/025
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR 2963170