×

Smoothed analysis for the condition number of structured real polynomial systems. (English) Zbl 1482.14062

The probabilistic analysis of condition numbers is of central importance to turn condition-based complexity analyses of numerical algorithsm into probabilistic complexity analyses. While the former explain how the algorithm behaves at a particular input, the former allows us to see how the algorithm behaves in general.
Unfortunately, passing from a condition-based complexity analysis to a probabilistic complexity analysis requires to choose a probabilistic distribution of the input. With the notable exception of numerical linear algebra and the theory of random matrices, probabilistic analyses of condition numbers in numerical algebraic geometry rely exclusively on some form of Gaussian assumption of the input.
In their previous paper [A. A. Ergür et al., Found. Comput. Math. 19, No. 1, 131–157 (2019; Zbl 1409.65033)], they performed an average complexity analysis in which they consider the condition number, as introduced in [F. Cucker et al., J. Complexity 24, No. 5–6, 582–605 (2008; Zbl 1166.65021)], of random real polynomial systems under robust assumptions. In this paper, they extend their results to the smoothed analysis framework of D. Spielman and S.-H. Teng [in: Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press. 296–305 (2001; Zbl 1323.68636)]. In these framework, we don’t just consider a random input, but an arbitrary input perturbed by random noise. As numerical algorithms work with inputs submitted to errors, this is a more realistic framwork.
Moreover, the authors do not only provide an smoothed complexity analysis, but they also do so for a class of estructured random polynomial systems. The structure is chosen by taking the random polynomials out of subspaces of the space of polynomials, for which one can guarantee nice evaluation bounds. This is the first probabilistic analysis for random structured polynomials.
Finally, let us note that to achive this, Ergür, Paouris and Rojas rely on results coming from geometric functional analysis for subgaussian and anti-concentrated random variables such as those in [R. Vershynin, High-dimensional probability. An introduction with applications in data science. Cambridge: Cambridge University Press (2018; Zbl 1430.60005); M. Rudelson and R. Vershynin, Int. Math. Res. Not. 2015, No. 19, 9594–9617 (2015; Zbl 1330.60029)].

MSC:

14Q65 Geometric aspects of numerical algebraic geometry
65F35 Numerical computation of matrix norms, conditioning, scaling
14P99 Real algebraic and real-analytic geometry
65Y20 Complexity and performance of numerical algorithms

Software:

CHomP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Beltr\'{a}n, Carlos; Pardo, Luis Miguel, Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J. Amer. Math. Soc., 22, 2, 363-385 (2009) · Zbl 1206.90173 · doi:10.1090/S0894-0347-08-00630-9
[2] Blum, Lenore; Cucker, Felipe; Shub, Michael; Smale, Steve, Complexity and real computation, xvi+453 pp. (1998), Springer-Verlag, New York · Zbl 0948.68068 · doi:10.1007/978-1-4612-0701-6
[3] B\"{u}rgisser, Peter; Cucker, Felipe, Condition, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 349, xxxii+554 pp. (2013), Springer, Heidelberg · Zbl 1280.65041 · doi:10.1007/978-3-642-38896-5
[4] B\"{u}rgisser, Peter; Cucker, Felipe; Lairez, Pierre, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM, 66, 1, Art. 5, 30 pp. (2019) · Zbl 1426.14016 · doi:10.1145/3275242
[5] B\"{u}rgisser, Peter; Cucker, Felipe; Tonelli-Cueto, Josu\'{e}, Computing the homology of semialgebraic sets. I: Lax formulas, Found. Comput. Math., 20, 1, 71-118 (2020) · Zbl 1440.14264 · doi:10.1007/s10208-019-09418-y
[6] Cucker, Felipe, Approximate zeros and condition numbers, J. Complexity, 15, 2, 214-226 (1999) · Zbl 0967.65063 · doi:10.1006/jcom.1999.0503
[7] Cucker, Felipe; Erg\"{u}r, Alperen A.; Tonelli-Cueto, Josue, Plantinga-Vegter algorithm takes average polynomial time. ISSAC’19-Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation, 114-121 (2019), ACM, New York · Zbl 1467.14150
[8] Cucker, Felipe; Krick, Teresa; Malajovich, Gregorio; Wschebor, Mario, A numerical algorithm for zero counting. I. Complexity and accuracy, J. Complexity, 24, 5-6, 582-605 (2008) · Zbl 1166.65021 · doi:10.1016/j.jco.2008.03.001
[9] Cucker, Felipe; Krick, Teresa; Malajovich, Gregorio; Wschebor, Mario, A numerical algorithm for zero counting. II. Distance to ill-posedness and smoothed analysis, J. Fixed Point Theory Appl., 6, 2, 285-294 (2009) · Zbl 1215.65218 · doi:10.1007/s11784-009-0127-4
[10] Cucker, Felipe; Krick, Teresa; Malajovich, Gregorio; Wschebor, Mario, A numerical algorithm for zero counting. III: Randomization and condition, Adv. in Appl. Math., 48, 1, 215-248 (2012) · Zbl 1245.65189 · doi:10.1016/j.aam.2011.07.001
[11] Cucker, Felipe; Krick, Teresa; Shub, Michael, Computing the homology of real projective sets, Found. Comput. Math., 18, 4, 929-970 (2018) · Zbl 1506.55014 · doi:10.1007/s10208-017-9358-8
[12] Dirksen, Sjoerd, Tail bounds via generic chaining, Electron. J. Probab., 20, no. 53, 29 pp. (2015) · Zbl 1327.60048 · doi:10.1214/EJP.v20-3760
[13] Erg\"{u}r, Alperen A.; Paouris, Grigoris; Rojas, J. Maurice, Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions, Found. Comput. Math., 19, 1, 131-157 (2019) · Zbl 1409.65033 · doi:10.1007/s10208-018-9380-5
[14] Hoeffding, Wassily, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602
[15] Kellogg, O. D., On bounded polynomials in several variables, Math. Z., 27, 1, 55-64 (1928) · JFM 53.0082.03 · doi:10.1007/BF01171085
[16] Klartag, B.; Mendelson, S., Empirical processes and random projections, J. Funct. Anal., 225, 1, 229-245 (2005) · Zbl 1079.60033 · doi:10.1016/j.jfa.2004.10.009
[17] Lairez, Pierre, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Found. Comput. Math., 17, 5, 1265-1292 (2017) · Zbl 1458.65058 · doi:10.1007/s10208-016-9319-7
[18] Liaw, Christopher; Mehrabian, Abbas; Plan, Yaniv; Vershynin, Roman, A simple tool for bounding the deviation of random matrices on geometric sets. Geometric aspects of functional analysis, Lecture Notes in Math. 2169, 277-299 (2017), Springer, Cham · Zbl 1366.60011
[19] Livshyts, Galyna; Paouris, Grigoris; Pivovarov, Peter, On sharp bounds for marginal densities of product measures, Israel J. Math., 216, 2, 877-889 (2016) · Zbl 1373.60046 · doi:10.1007/s11856-016-1431-5
[20] Nguyen, Hoi H., On a condition number of general random polynomial systems, Math. Comp., 85, 298, 737-757 (2016) · Zbl 1331.12003 · doi:10.1090/mcom/2993
[21] Paouris, Grigoris; Pivovarov, Peter, Randomized isoperimetric inequalities. Convexity and concentration, IMA Vol. Math. Appl. 161, 391-425 (2017), Springer, New York · Zbl 1381.52014
[22] Rudelson, Mark; Vershynin, Roman, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math., 218, 2, 600-633 (2008) · Zbl 1139.15015 · doi:10.1016/j.aim.2008.01.010
[23] Rudelson, Mark; Vershynin, Roman, Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math., 62, 12, 1707-1739 (2009) · Zbl 1183.15031 · doi:10.1002/cpa.20294
[24] Rudelson, Mark; Vershynin, Roman, Small ball probabilities for linear images of high-dimensional distributions, Int. Math. Res. Not. IMRN, 19, 9594-9617 (2015) · Zbl 1330.60029 · doi:10.1093/imrn/rnu243
[25] Schechtman, Gideon, Two observations regarding embedding subsets of Euclidean spaces in normed spaces, Adv. Math., 200, 1, 125-135 (2006) · Zbl 1108.46011 · doi:10.1016/j.aim.2004.11.003
[26] Shub, Michael; Smale, Steve, Complexity of B\'{e}zout’s theorem. I. Geometric aspects, J. Amer. Math. Soc., 6, 2, 459-501 (1993) · Zbl 0821.65035 · doi:10.2307/2152805
[27] Smale, Steve, Mathematical problems for the next century, Math. Intelligencer, 20, 2, 7-15 (1998) · Zbl 0947.01011 · doi:10.1007/BF03025291
[28] Spielman, Daniel A.; Teng, Shang-Hua, Smoothed analysis of algorithms. Proceedings of the International Congress of Mathematicians, Vol. I, Beijing, 2002, 597-606 (2002), Higher Ed. Press, Beijing · Zbl 1056.65148
[29] Talagrand, Michel, The generic chaining, Springer Monographs in Mathematics, viii+222 pp. (2005), Springer-Verlag, Berlin · Zbl 1075.60001
[30] Vershynin, Roman, High-dimensional probability, Cambridge Series in Statistical and Probabilistic Mathematics 47, xiv+284 pp. (2018), Cambridge University Press, Cambridge · Zbl 1430.60005 · doi:10.1017/9781108231596
[31] Vershynin, Roman, Four lectures on probabilistic methods for data science. The mathematics of data, IAS/Park City Math. Ser. 25, 231-271 (2018), Amer. Math. Soc., Providence, RI · Zbl 1404.68012 · doi:10.1090/pcms/025
[32] Vershynin, Roman, Introduction to the non-asymptotic analysis of random matrices. Compressed sensing, 210-268 (2012), Cambridge Univ. Press, Cambridge
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.