Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis
share
We consider the sensitivity of real zeros of polynomial systems with respect to perturbation of the coefficients, and extend our earlier probabilistic estimates for the condition number in two directions: (1) We give refined bounds for the condition number of random structured polynomial systems, depending on a variant of sparsity and an intrinsic geometric quantity called dispersion. (2) Given any structured polynomial system P, we prove the existence of a nearby well-conditioned structured polynomial system Q, with explicit quantitative estimates. Our underlying notion of structure is to consider a linear subspace E_i of the space H_d_i of homogeneous n-variate polynomials of degree d_i, let our polynomial system P be an element of E:=E_1×...× E_n-1, and let (E):=(E_1) +...+(E_n-1) be our measure of sparsity. The dispersion σ(E) provides a rough measure of how suitable the tuple E is for numerical solving. Part I of this series studied how to extend probabilistic estimates of a condition number defined by Cucker to a family of measures going beyond the weighted Gaussians often considered in the current literature. We continue at this level of generality, using tools from geometric functional analysis.
READ FULL TEXT