## 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
**HTML**| PDF - Math. Comp.
**90**(2021), 2161-2184 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**

## Additional Information

**Alperen A. Ergür**- Affiliation: Technische Universitat Berlin, Institut für Mathematik, Sekretariat MA 3-2, Strasse des 17. Juni 136 10623 Berlin, Germany
- Address at time of publication: Mathematics Department, University of Texas at San Antonio, One UTSA Circle, San Antonio, Texas 78249
- Email: alperen.ergur@utsa.edu
**Grigoris Paouris**- Affiliation: Department of Mathematics, Texas A&M University TAMU 3368, College Station, Texas 77843-3368
- MR Author ID: 671202
- Email: grigoris@math.tamu.edu
**J. Maurice Rojas**- Affiliation: Department of Mathematics, Texas A&M University TAMU 3368, College Station, Texas 77843-3368
- MR Author ID: 354192
- ORCID: 0000-0002-1657-2674
- Email: rojas@math.tamu.edu
- Received by editor(s): December 13, 2018
- Received by editor(s) in revised form: July 26, 2019, February 17, 2020, and July 27, 2020
- Published electronically: June 18, 2021
- Additional Notes: The first author was partially supported by Einstein Foundation, Berlin and by Pravesh Kothari of CMU. The second author was partially supported by Simons Foundation Collaboration grant 527498 and NSF grants DMS-1812240 and CCF-1900881. The third author was partially supported by NSF grants CCF-1409020, DMS-1460766, and CCF-1900881
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp.
**90**(2021), 2161-2184 - MSC (2020): Primary 65Y20; Secondary 51F99
- DOI: https://doi.org/10.1090/mcom/3647
- MathSciNet review: 4280296