On the number of minima of a random polynomial

DOI10.1016/J.JCO.2007.09.003MaRDI QIDQ2483199zbMATH OpenOpenAlexFDO

Authors Jean-Pierre Dedieu, Gregorio Malajovich

Publication date 28 April 2008

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0702360

zbMATH Keywords

critical pointsnumber of maximanumber of minimarandom polynomials

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Large deviations (60F10) Random operators and equations (aspects of stochastic analysis) (60H25) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Numerical computation of solutions to single equations (65H05)

Abstract: We give an upper bound in O(d ^((n+1)/2)) for the number of critical points of a normal random polynomial with degree d and at most n variables. Using the large deviation principle for the spectral value of large random matrices we obtain the bound O(exp(-beta n^2 + (n/2) log (d-1))) (beta is a positive constant independent on n and d) for the number of minima of such a polynomial. This proves that most normal random polynomials of fixed degree have only saddle points. Finally, we give a closed form expression for the number of maxima (resp. minima) of a random univariate polynomial, in terms of hypergeometric functions.

Review text

A random polynomial \(f\) over the reals with \(n\) variables and degree \(d\geq 2\) is considered. The problem is to compute, on average, the number of its critical points (the number of real roots of the system \(Df(x)= 0\)). It is proved; that the upper bound for the expected number of such critical points is \(\sqrt{2}\cdot(d- 1)^{(n+1)/2}\). Using the large deviation principle for the spectral value of large random matrices the upper bound \(K\cdot\exp(-n{\ln(3)\over 4}+{n+ 1\over 2})\ln(d- 1)\) is also derived, where \(K\) is a positive constant. This result indicates that most random polynomials of fixed degree have only saddle-points, which are neither local minima nor maxima. A closed form expression for the expected number of minima (resp. maxima) in terms of hypergeometric functions is also given.

Recommendations

• The expected number of local maxima of a random algebraic polynomial
• What is the Least Expected Number of Real Roots of a Random Polynomial?
• scientific article; zbMATH DE number 1859213
• Random polynomials having few or no real zeros
• Betti numbers of random real hypersurfaces and determinants of random symmetric matrices

Cites work

• Distribution of roots of random polynomials
• Erratum to “How many zeros of a random polynomial are real?”
• High probability analysis of the condition number of sparse polynomial systems
• scientific article; zbMATH DE number 421657 (Why is no real title available?)
• scientific article; zbMATH DE number 51346 (Why is no real title available?)
• scientific article; zbMATH DE number 953040 (Why is no real title available?)
• scientific article; zbMATH DE number 1859213 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• scientific article; zbMATH DE number 3280855 (Why is no real title available?)
• Large deviations and stochastic calculus for large random matrices
• Large Deviations of Extreme Eigenvalues of Random Matrices
• On the average number of real roots of a random algebraic equation
• On the Average Number of Real Roots of a Random Algebraic Equation (II)
• On the Kostlan-Shub-Smale model for random polynomial systems. Variance of the number of roots
• On the roots of a random system of equations. The theorem of Shub and Smale and some extensions
• Random systems of polynomial equations. The expected number of roots under smooth analysis

Cited in

(14)

• Expected number of critical points of random holomorphic sections over complex projective space
• On the expected number of zeros of nonlinear equations
• Extrema of a real polynomial
• Low-degree approximation of random polynomials
• Betti numbers of random real hypersurfaces and determinants of random symmetric matrices
• Expected topology of random real algebraic submanifolds
• Statistics of stationary points of random finite polynomial potentials
• On the complex points of random polynomials
• Quantitative singularity theory for random polynomials
• On the measure of polynomials attaining maxima on a vertex
• Statistics on Hilbert's 16th problem
• Random systems of polynomial equations. The expected number of roots under smooth analysis
• On the topological degree of the gradient of homogeneous Gaussian random polynomial
• On the probability distribution of data at points in real complete intersection varieties

This page was built for publication: On the number of minima of a random polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483199)