General formulas for the smoothed analysis of condition numbers. (English) Zbl 1121.65041
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.
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.
Reviewer: Udo Hertrich-Jeromin (Bath)
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 53C65 | Integral geometry |
| 53C20 | Global Riemannian geometry, including pinching |
| 14P05 | Real algebraic sets |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
condition number; smoothed analysis estimate; tube; real algebraic variety; ill-posed problem; linear equation; eigenvaluesReferences:
| [1] | P. Bürgisser, F. Cucker, M. Lotz, Smoothed analysis of complex conic condition numbers, Preprint, 2006; P. Bürgisser, F. Cucker, M. Lotz, Smoothed analysis of complex conic condition numbers, Preprint, 2006 · Zbl 1113.65044 |
| [2] | Chern, S.-S., On the kinematic formula in integral geometry, J. Math. Mech., 16, 101-118 (1966) · Zbl 0142.20704 |
| [3] | Demmel, J., The probability that a numerical analysis problem is difficult, Math. Comp., 50, 449-480 (1988) · Zbl 0657.65066 |
| [4] | Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 211-218 (1936) · JFM 62.1075.02 |
| [5] | Gray, A., Tubes, Addison-Wesley Publishing Company Advanced Book Program (1990), Addison-Wesley: Addison-Wesley Redwood City, CA · Zbl 0692.53001 |
| [6] | Howard, R., The kinematic formula in Riemannian homogeneous spaces, Mem. Amer. Math. Soc., 106, 509, vi+69 (1993) · Zbl 0810.53057 |
| [7] | Milnor, J., On the Betti numbers of real varieties, Proc. Amer. Math. Soc., 15, 275-280 (1964) · Zbl 0123.38302 |
| [8] | Santaló, L. A., Integral Geometry and Geometric Probability (1976), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, MA · Zbl 0342.53049 |
| [9] | D.A. Spielman, S.-H. Teng, Smoothed analysis of algorithms, in: Proceedings of the International Congress of Mathematicians, vol. I, 2002, pp. 597-606; D.A. Spielman, S.-H. Teng, Smoothed analysis of algorithms, in: Proceedings of the International Congress of Mathematicians, vol. I, 2002, pp. 597-606 · Zbl 1056.65148 |
| [10] | Spivak, M., A Comprehensive Introduction to Differential Geometry, vol. III (1979), Publish or Perish Inc.: Publish or Perish Inc. Wilmington, DE · Zbl 0439.53003 |
| [11] | Weyl, H., On the volume of tubes, Amer. J. Math., 61, 2, 461-472 (1939) · JFM 65.0796.01 |
| [12] | Wilkinson, J., Note on matrices with a very ill-conditioned eigenproblem, Numer. Math., 19, 176-178 (1972) · Zbl 0252.65027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
