On mixed and componentwise condition numbers for Moore–Penrose inverse and linear least squares problems
HTML articles powered by AMS MathViewer
- by Felipe Cucker, Huaian Diao and Yimin Wei PDF
- Math. Comp. 76 (2007), 947-963 Request permission
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.References
- M. Arioli, I. S. Duff, and P. P. M. de Rijk, On the augmented system approach to sparse least-squares problems, Numer. Math. 55 (1989), no. 6, 667–684. MR 1005065, DOI 10.1007/BF01389335
- Adi Ben-Israel and Thomas N. E. Greville, Generalized inverses, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 15, Springer-Verlag, New York, 2003. Theory and applications. MR 1987382
- Å. Björck, Component-wise perturbation analysis and error bounds for linear least squares solutions, BIT 31 (1991), no. 2, 238–244. MR 1112220, DOI 10.1007/BF01931284
- James W. Demmel and Nicholas J. Higham, Improved error bounds for underdetermined system solvers, SIAM J. Matrix Anal. Appl. 14 (1993), no. 1, 1–14. MR 1199540, DOI 10.1137/0614001
- A. J. Geurts, A contribution to the theory of condition, Numer. Math. 39 (1982), no. 1, 85–96. MR 664538, DOI 10.1007/BF01399313
- I. Gohberg and I. Koltracht, Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl. 14 (1993), no. 3, 688–704. MR 1227773, DOI 10.1137/0614049
- Alexander Graham, Kronecker products and matrix calculus: with applications, Ellis Horwood Series in Mathematics and its Applications, Ellis Horwood Ltd., Chichester; Halsted Press [John Wiley & Sons, Inc.], New York, 1981. MR 640865
- S. Gratton, On the condition number of linear least squares problems in a weighted Frobenius norm, BIT 36 (1996), no. 3, 523–530. International Linear Algebra Year (Toulouse, 1995). MR 1410095, DOI 10.1007/BF01731931
- J.F. Grcar, Optimal sensitivity analysis of linear least squares, Lawrence Berkeley National Laboratory, Report LBNL-52434, 2003.
- Nicholas J. Higham, A survey of componentwise perturbation theory in numerical linear algebra, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993) Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 49–77. MR 1314843, DOI 10.1090/psapm/048/1314843
- 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, 1186–1196. MR 2003329, DOI 10.1137/S0895479801389564
- John R. Rice, A theory of condition, SIAM J. Numer. Anal. 3 (1966), 287–310. MR 211576, DOI 10.1137/0703023
- J. Rohn, New condition numbers for matrices and linear systems, Computing 41 (1989), no. 1-2, 167–169 (English, with German summary). MR 981682, DOI 10.1007/BF02238741
- Robert D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach. 26 (1979), no. 3, 494–526. MR 535268, DOI 10.1145/322139.322148
- G. W. Stewart, On the perturbation of pseudo-inverses, projections and linear least squares problems, SIAM Rev. 19 (1977), no. 4, 634–662. MR 461871, DOI 10.1137/1019104
- G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
- G. Wang, Y. Wei and S. Qiao, Generalized Inverses: Theory and Computations, Science Press, Beijing/New York, 2004.
- P.Å. Wedin, Perturbation theory for pseudo-inverses, BIT, 13(1973), pp. 217-232.
Additional Information
- 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
- Received by editor(s): July 21, 2005
- Received by editor(s) in revised form: November 23, 2005
- Published electronically: 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 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 76 (2007), 947-963
- MSC (2000): Primary 15A09, 15A12; Secondary 65F35
- DOI: https://doi.org/10.1090/S0025-5718-06-01913-2
- MathSciNet review: 2291844