TU Berlin

Fachgebiet Algorithmische AlgebraRefereed Contributions

Page Content

to Navigation

There is no English translation for this web page.

Refereed Contributions

Smoothed Analysis of Condition Numbers
Citation key B-Smoothed-Analysis-Of-Condition-Numbers-1
Author Peter Bürgisser
Title of Book Foundations of Computational Mathematics
Pages 1- 41
Year 2009
Address Hong Kong
Number 363
Editor Felipe Cucker and Allan Pinkus and Michael Jeremy Todd
Publisher Cambridge University Press
Series London Mathematical Society Lecture Note Series
Abstract The running time of many iterative numerical algorithms is dominated by the condition number of the input, a quantity measuring the sensitivity of the solution with regard to small perturbations of the input. Examples are iterative methods of linear algebra, interior-point methods of linear and convex optimization, as well as homotopy methods for solving systems of polynomial equations. Thus a probabilistic analysis of these algorithms can be reduced to the analysis of the distribution of the condition number for a random input. This approach was elaborated for average-case complexity by many researchers. The goal of this survey is to explain how average-case analysis can be naturally refined in the sense of smoothed analysis. The latter concept, introduced by Spielman and Teng in 2001, aims at showing that for all real inputs (even ill-posed ones), and all slight random perturbations of that input, it is unlikely that the running time will be large. A recent general result of Bürgisser, Cucker and Lotz (2008) gives smoothed analysis estimates for a variety of applications. Its proof boils down to local bounds on the volume of tubes around a real algebraic hypersurface in a sphere. This is achieved by bounding the integrals of absolute curvature of smooth hypersurfaces in terms of their degree via the principal kinematic formula of integral geometry and Bezout's theorem.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe