Mathematics of Computation

On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems

Author(s): Felipe Cucker; Huaian Diao; Yimin Wei.
Journal: Math. Comp. 76 (2007), 947-963.
MSC (2000): Primary 15A09, 15A12; Secondary 65F35
Posted: November 2, 2006
Retrieve article in: PDF DVI PostScript

Abstract: Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using some norms. To take into account the relative of each data component, and, in particular, a possible data sparseness, componentwise condition numbers have been increasingly considered. These are mostly of two kinds: mixed and componentwise. In this paper, we give explicit expressions, computable from the data, for the mixed and componentwise condition numbers for the computation of the Moore-Penrose inverse as well as for the computation of solutions and residues of linear least squares problems. In both cases the data matrices have full column (row) rank.

1.: M. Arioli, I.S. Duff and P.P.M. de Rijk, An augmented system approach to sparse least-squares problems, Numer. Math. 55(1989), pp. 667-684. MR 1005065 (90g:65048)
2.: A. Ben-Israel and T.N.E. Greville, Generalized Inverses: Theory and Applications, 2nd Edition, Springer Verlag, New York, 2003. MR 1987382 (2004b:15008)
3.: Å. Björck, Component-wise perturbation analysis and error bounds for linear least squares solutions, BIT, 31(1991), pp. 238-244. MR 1112220 (92i:65079)
4.: J. Demmel and N. Higham, Improved error bounds for underdetermined system solvers, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 1-14. MR 1199540 (94c:65050)
5.: A.J. Geurts, A Contribution to the theory of condition, Numer. Math., 39(1982), pp. 85-96. MR 0664538 (83g:65046)
6.: I. Gohberg and I. Koltracht, Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl., 14(1993), pp. 688-704. MR 1227773 (94j:65062)
7.: A. Graham, Kronecker Products and Matrix Calculus with Application, Wiley, New York, 1981. MR 0640865 (83g:15001)
8.: S. Gratton, On the condition number of linear least squares problems in a weighted Frobenius norm, BIT, 36(1996), no.3, pp. 523-530. MR 1410095 (97h:65050)
9.: J.F. Grcar, Optimal sensitivity analysis of linear least squares, Lawrence Berkeley National Laboratory, Report LBNL-52434, 2003.
10.: N.J. Higham, A survey of componentwise perturbation theory in numerical linear algebra, Proceedings of Symposia in Applied Mathematics, Vol.48, 1994, pp. 49-77. MR 1314843 (96a:65065)
11.: A.N. Malyshev, A unified theory of conditioning for linear least squares and Tikhonov regularization solutions, SIAM J. Matrix Anal. Appl., 24(2003), no.4, pp. 1186-1196. MR 2003329 (2004f:65052)
12.: J.R. Rice, A theory of condition, SIAM J. Numer. Anal., 3(1966), pp. 217-232. MR 0211576 (35:2454)
13.: J. Rohn, New condition numbers for matrices and linear systems, Computing, 41(1989), pp. 167-169. MR 0981682 (90a:65104)
14.: R.D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26(1979), No.3, pp. 817-526. MR 0535268 (80e:65051)
15.: G.W. Stewart, On the perturbation of pseudo-inverses, projections and linear least sqaures problems, SIAM Rev., 19 (1977), pp. 634-662. MR 0461871 (57:1854)
16.: G.W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Academic Press, New York, 1990. MR 1061154 (92a:65017)
17.: G. Wang, Y. Wei and S. Qiao, Generalized Inverses: Theory and Computations, Science Press, Beijing/New York, 2004.
18.: P.Å. Wedin, Perturbation theory for pseudo-inverses, BIT, 13(1973), pp. 217-232.

Retrieve articles in Mathematics of Computation with MSC (2000): 15A09, 15A12, 65F35

Felipe Cucker
Affiliation: Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon Tong, Hong Kong, P.R. of China
Email: macucker@math.cityu.edu.hk

Huaian Diao
Affiliation: Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon Tong, Hong Kong, P.R. of China
Email: 50007445@student.cityu.edu.hk

Yimin Wei
Affiliation: School of Mathematical Sciences, Fudan University, Shanghai 200433 and Key Laboratory of Mathematics for Nonlinear Sciences (Fudan University), Ministry of Education, P.R. of China
Email: ymwei@fudan.edu.cn

DOI: 10.1090/S0025-5718-06-01913-2
PII: S 0025-5718(06)01913-2
Keywords: Condition numbers, componentwise analysis, least squares
Received by editor(s): July 21, 2005
Received by editor(s) in revised form: November 23, 2005
Posted: November 2, 2006
Additional Notes: The first author was partially supported by City University SRG grant 7001860.
The third author was partially supported by the National Natural Science Foundation of China under grant 10471027 and Shanghai Education Committee.
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS