nach oben

Foundations of Computational Mathematics

Erschienen in:

31.01.2018

Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions

verfasst von: Alperen A. Ergür, Grigoris Paouris, J. Maurice Rojas

Erschienen in: Foundations of Computational Mathematics | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider the sensitivity of real roots of polynomial systems with respect to perturbations of the coefficients. In particular—for a version of the condition number defined by Cucker and used later by Cucker, Krick, Malajovich, and Wschebor—we establish new probabilistic estimates that allow a much broader family of measures than considered earlier. We also generalize further by allowing overdetermined systems. In Part II, we study smoothed complexity and how sparsity (in the sense of restricting which terms can appear) can help further improve earlier condition number estimates.

Vorheriger Artikel Tropical Coordinates on the Space of Persistence Barcodes

Nächster Artikel On the Dirac–Frenkel Variational Principle on Tensor Banach Spaces

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Here, “complexity” simply means the total number of field operations over \(\mathbb {C}\) needed to find a start point \(x_0\) for Newton’s iteration, such that the sequence of Newton iterates \((x_n)_{n\in \mathbb {N}}\) converges to a true root \(\zeta \) of P (see, e.g., [3, Ch. 8]) at the rate of \(|x_n-\zeta | \le (1/2)^{2^{n-1}}|x_0-\zeta |\) or faster.

Franck Barthe and Alexander Koldobsky, “Extremal slabs in the cube and the Laplace transform,” Adv. Math. 174 (2003), pp. 89–114.MathSciNetCrossRefMATH

Carlos Beltrán and Luis-Miguel Pardo, “Smale’s 17th problem: Average polynomial time to compute affine and projective solutions,” Journal of the American Mathematical Society 22 (2009), pp. 363–385.MathSciNetCrossRefMATH

Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale, Complexity and Real Computation, Springer-Verlag, 1998.

Jean Bourgain, “On the isotropy-constant problem for \(\psi _2\) -bodies,” in Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 1807, pp. 114–121, Springer Berlin Heidielberg, 2003.

Peter Bürgisser and Felipe Cucker, “On a problem posed by Steve Smale,” Annals of Mathematics, pp. 1785–1836, Vol. 174 (2011), no. 3.

Peter Bürgisser and Felipe Cucker, Condition, Grundlehren der mathematischen Wissenschaften, no. 349, Springer-Verlag, 2013.

John F. Canny, The Complexity of Robot Motion Planning, ACM Doctoral Dissertation Award Series, MIT Press, 1987.

Peter Bürgisser; Felipe Cucker; and Pierre Lairez, “Computing the homology of basic semialgebraic sets in weakly exponential time,” Math ArXiV preprint arXiv:1706.07473.

D. Castro, Juan San Martín, Luis M. Pardo, “Systems of Rational Polynomial Equations have Polynomial Size Approximate Zeros on the Average,” Journal of Complexity 19 (2003), pp. 161–209.

10.

Felipe Cucker, “Approximate zeros and condition numbers,” Journal of Complexity 15 (1999), no. 2, pp. 214–226.MathSciNetCrossRefMATH

11.

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, pp. 582–605MathSciNetCrossRefMATH

12.

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, pp. 285–294.MathSciNetCrossRefMATH

13.

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, pp. 215–248.MathSciNetCrossRefMATH

14.

Felipe Cucker; Teresa Krick; and Mike Shub, “Computing the Homology of Real Projective Sets,” Found. Comp. Math., to appear. (Earlier version available as Math ArXiV preprint arXiv:1602.02094.)

15.

Nikos Dafnis and Grigoris Paouris, “Small ball probability estimates, \(\Psi _2\) -behavior and the hyperplane conjecture,” Journal of Functional Analysis 258 (2010), pp. 1933–1964.MathSciNetCrossRefMATH

16.

Jean-Piere Dedieu, Mike Shub, “Newton’s Method for Overdetermined Systems Of Equations,” Math. Comp. 69 (2000), no. 231, pp. 1099–1115.MathSciNetCrossRefMATH

17.

James Demmel, Benjamin Diament, and Gregorio Malajovich, “On the Complexity of Computing Error Bounds,” Found. Comput. Math. pp. 101–125 (2001).

18.

Wassily Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, 58 (301):13–30, 1963.MathSciNetCrossRefMATH

19.

O. D. Kellog, “On bounded polynomials in several variables,” Mathematische Zeitschrift, December 1928, Volume 27, Issue 1, pp. 55–64.MathSciNetCrossRef

20.

Bo’az Klartag and Emanuel Milman, “Centroid bodies and the logarithmic Laplace Transform – a unified approach,” J. Func. Anal., 262(1):10–34, 2012.MathSciNetCrossRefMATH

21.

Alexander Koldobsky and Alain Pajor, “A Remark on Measures of Sections of \(L_p\) -balls,” Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics 2169, pp. 213–220, Springer-Verlag, 2017.

22.

Eric Kostlan, “On the Distribution of Roots of Random Polynomials,” Ch. 38 (pp. 419–431) of From Topology to Computation: Proceedings of Smalefest (M. W. Hirsch, J. E. Marsden, and M. Shub, eds.), Springer-Verlag, New York, 1993.

23.

Pierre Lairez, “A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time,” Foundations of Computational Mathematics, https://doi.org/10.1007/s10208-016-9319-7.

24.

G. Livshyts, Grigoris Paouris and P. Pivovarov, “Sharp bounds for marginal densities of product measures,” Israel Journal of Mathematics, Vol. 216, Issue 2, pp. 877–889.

25.

G. Paouris and P. Pivovarov, “Randomized Isoperimetric Inequalities”, IMA Volume “Discrete Structures: Analysis and Applications” (Springer)

26.

Hoi H. Nguyen, “On a condition number of general random polynomial systems,” Mathematics of Computation (2016) 85, pp. 737–757MathSciNetCrossRefMATH

27.

Mark Rudelson and Roman Vershynin, “The Littlewood-Offord Problem and Invertibility of Random Matrices,” Adv. Math. 218 (2008), no. 2, pp. 600–633.MathSciNetCrossRefMATH

28.

Mark Rudelson and Roman Vershynin, “The Smallest Singular Value of Rectangular Matrix,” Communications on Pure and Applied Mathematics 62 (2009), pp. 1707–1739.MathSciNetCrossRefMATH

29.

Mark Rudelson and Roman Vershynin, “Small ball Probabilities for Linear Images of High-Dimensional Distributions,” Int. Math. Res. Not. (2015), no. 19, pp. 9594–9617.

30.

Roman Vershynin , “High Dimensional Probability: An Introduction with Application in Data Science”, available at https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf

31.

Roman Vershynin , “Four Lectures on Probabilistic Methods for Data Science”, available at https://www.math.uci.edu/~rvershyn/papers/four-lectures-probability-data.pdf

32.

Igor R. Shafarevich, Basic Algebraic Geometry 1: Varieties in Projective Space, 3rd edition, Springer-Verlag (2013).

33.

Mike Shub and Steve Smale, “Complexity of Bezout’s Theorem I. Geometric Aspects,” J. Amer. Math. Soc. 6 (1993), no. 2, pp. 459–501.MathSciNetMATH

34.

Roman Vershynin, “Introduction to the Non-Asymptotic Analysis of Random Matrices,” Compressed sensing, pp. 210–268, Cambridge Univ. Press, Cambridge, 2012.

35.

Assaf Naor and Artem Zvavitch, “Isomorphic embedding of \(\ell _p^n\), \(1 < p < 2\), into \(\ell _1^{(1+\varepsilon )n}\) ,” Israel J. Math. 122 (2001), pp. 371–380.

Titel: Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions
verfasst von: Alperen A. Ergür
Grigoris Paouris
J. Maurice Rojas
Publikationsdatum: 31.01.2018
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 1/2019
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-018-9380-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2019

A Polynomial Rate of Asymptotic Regularity for Compositions of Projections in Hilbert Space

Correction to: On the Stability and Accuracy of Least Squares Approximations

Correction to: Finite Element Approximation of the Spectrum of the Curl Operator in a Multiply Connected Domain

Complexity of Sparse Polynomial Solving: Homotopy on Toric Varieties and the Condition Metric

Tropical Coordinates on the Space of Persistence Barcodes

Correction to: On Post-Lie Algebras, Lie–Butcher Series and Moving Frames

Premium Partner