General formulas for the smoothed analysis of condition numbers (Q2499745)

The main result of this short article provides smoothed analysis estimates for a conic condition number, where the set of ill-posed inputs is contained in the zero set of a homogeneous polynomial. The problems of solving a linear equation (condition number of a square matrix) and of finding the eigenvalues of a matrix are briefly discussed as applications. The authors then reformulate one of the estimates as an estimate of the volume of the intersection of a tube about a real algebraic subvariety and a ball, where the bounds are given in terms of the the radius of the ball, the degree of the polynomial defining the subvariety and the ambient dimension. The second half of the article is devoted to a sketch of proof of this latter estimate.