Numerical Analysis
Upper bounds on the distribution of the condition number of singular matrices
Comptes Rendus. Mathématique, Volume 340 (2005) no. 12, pp. 915-919.

We exhibit upper bounds for the probability distribution of the generalized condition number of singular complex matrices. To this end, we develop a new technique to study volumes of tubes about projective varieties in the complex projective space. As a main outcome, we show an upper bound estimate for the volume of the intersection of a tube with an equi-dimensional projective algebraic variety.

Nous exhibons des bornes de la fonction de distribution du conditionnement des matrices singulières. Pour ce but nous developpons une technique nouvelle pour analyser les volumes des tubes (par rapport a la distance de Fubini–Study) autour des sous-variétés algèbriques d'un espace projectif complex. Plus spécifiquement, nous demontrons des bornes supérieueres de volumes des intersections des tubes extrinsèques (autour des sous-variétés algébriques avec une autre variété algèbrique donnée).

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2005.05.012
Beltrán, Carlos 1; Pardo, Luis Miguel 1

1 Departamento de Matemáticas, Estadística y Computación, F. de Ciencias, Universidad de Cantabria, 39071 Santander, Spain
@article{CRMATH_2005__340_12_915_0,
     author = {Beltr\'an, Carlos and Pardo, Luis Miguel},
     title = {Upper bounds on the distribution of the condition number of singular matrices},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {915--919},
     publisher = {Elsevier},
     volume = {340},
     number = {12},
     year = {2005},
     doi = {10.1016/j.crma.2005.05.012},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1016/j.crma.2005.05.012/}
}
TY  - JOUR
AU  - Beltrán, Carlos
AU  - Pardo, Luis Miguel
TI  - Upper bounds on the distribution of the condition number of singular matrices
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 915
EP  - 919
VL  - 340
IS  - 12
PB  - Elsevier
UR  - http://archive.numdam.org/articles/10.1016/j.crma.2005.05.012/
DO  - 10.1016/j.crma.2005.05.012
LA  - en
ID  - CRMATH_2005__340_12_915_0
ER  - 
%0 Journal Article
%A Beltrán, Carlos
%A Pardo, Luis Miguel
%T Upper bounds on the distribution of the condition number of singular matrices
%J Comptes Rendus. Mathématique
%D 2005
%P 915-919
%V 340
%N 12
%I Elsevier
%U http://archive.numdam.org/articles/10.1016/j.crma.2005.05.012/
%R 10.1016/j.crma.2005.05.012
%G en
%F CRMATH_2005__340_12_915_0
Beltrán, Carlos; Pardo, Luis Miguel. Upper bounds on the distribution of the condition number of singular matrices. Comptes Rendus. Mathématique, Volume 340 (2005) no. 12, pp. 915-919. doi : 10.1016/j.crma.2005.05.012. http://archive.numdam.org/articles/10.1016/j.crma.2005.05.012/

[1] Castro, D.; Montaña, J.L.; Pardo, L.M.; San Martín, J. The distribution of condition numbers of rational data of bounded bit length, Found. Comput. Math., Volume 2 (2002), pp. 1-52

[2] Demmel, J.W. The probability that a numerical analysis problem is difficult, Math. Comp., Volume 50 (1988), pp. 449-480

[3] Eckart, C.; Young, G. The approximation of one matrix by another of lower rank, Psychometrika, Volume 1 (1936), pp. 211-218

[4] Edelman, A. Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., Volume 9 (1988), pp. 543-560

[5] Edelman, A. On the distribution of a scaled condition number, Math. Comp., Volume 58 (1992), pp. 185-190

[6] Fulton, W. Intersection Theory, Ergeb. Math. Grenzgeb. (3) [Results in Mathematics and Related Areas (3)], vol. 2, Springer-Verlag, Berlin, 1984

[7] Golub, G.H.; Van Loan, C.F. Matrix Computations, Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 1996

[8] Gray, A. Volumes of tubes about complex submanifolds of complex projective space, Trans. Amer. Math. Soc., Volume 291 (1985), pp. 437-449

[9] Gray, A. Tubes, Progr. Math., vol. 221, Birkhäuser, Basel, 2004

[10] Heintz, J. Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., Volume 24 (1983), pp. 239-277

[11] Higham, N.J. Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002

[12] W. Kahan, Huge generalized inverses of rank-deficient matrices, Unpublished manuscript

[13] Mirsky, L. Results and problems in the theory of doubly-stochastic matrices, Z. Wahrscheinlichkeitstheorie Verw. Gebiete, Volume 1 (1962/1963), pp. 319-334

[14] Schmidt, E. Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Tiel. Entwicklung willkurlichen Funktionen nach System vorgeschriebener, Maht. Ann., Volume 63 (1907), pp. 433-476

[15] Smale, S. On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.), Volume 13 (1985), pp. 87-121

[16] Stewart, G.W.; Sun, J.G. Matrix Perturbation Theory, Computer Sci. Sci. Comput., Academic Press, Boston, MA, 1990

[17] Trefethen, L.N.; Bau, D. Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997

[18] Turing, A.M. Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math., Volume 1 (1948), pp. 287-308

[19] von Neumann, J.; Goldstine, H.H. Numerical inverting of matrices of high order, Bull. Amer. Math. Soc., Volume 53 (1947), pp. 1021-1099

[20] Weyl, A. On the volume of tubes, Amer. J. Math., Volume 61 (1939), pp. 461-472

[21] Wilkinson, J.H. The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965

Cited by Sources:

Research was partially supported by MTM2004-01167.