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

Authors:
Felipe Cucker, Huaian Diao and Yimin Wei

Journal:
Math. Comp. **76** (2007), 947-963

MSC (2000):
Primary 15A09, 15A12; Secondary 65F35

Published electronically:
November 2, 2006

MathSciNet review:
2291844

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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,*On the augmented system approach to sparse least-squares problems*, Numer. Math.**55**(1989), no. 6, 667–684. MR**1005065**, 10.1007/BF01389335**2.**Adi Ben-Israel and Thomas N. E. Greville,*Generalized inverses*, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15, Springer-Verlag, New York, 2003. Theory and applications. MR**1987382****3.**Å. Björck,*Component-wise perturbation analysis and error bounds for linear least squares solutions*, BIT**31**(1991), no. 2, 238–244. MR**1112220**, 10.1007/BF01931284**4.**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**, 10.1137/0614001**5.**A. J. Geurts,*A contribution to the theory of condition*, Numer. Math.**39**(1982), no. 1, 85–96. MR**664538**, 10.1007/BF01399313**6.**I. Gohberg and I. Koltracht,*Mixed, componentwise, and structured condition numbers*, SIAM J. Matrix Anal. Appl.**14**(1993), no. 3, 688–704. MR**1227773**, 10.1137/0614049**7.**Alexander Graham,*Kronecker products and matrix calculus: with applications*, Ellis Horwood Ltd., Chichester; Halsted Press [John Wiley & Sons, Inc.], New York, 1981. Ellis Horwood Series in Mathematics and its Applications. MR**640865****8.**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**, 10.1007/BF01731931**9.**J.F. Grcar,*Optimal sensitivity analysis of linear least squares*, Lawrence Berkeley National Laboratory, Report LBNL-52434, 2003.**10.**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**, 10.1090/psapm/048/1314843**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, 1186–1196 (electronic). MR**2003329**, 10.1137/S0895479801389564**12.**John R. Rice,*A theory of condition*, SIAM J. Numer. Anal.**3**(1966), 287–310. MR**0211576****13.**J. Rohn,*New condition numbers for matrices and linear systems*, Computing**41**(1989), no. 1-2, 167–169 (English, with German summary). MR**981682**, 10.1007/BF02238741**14.**Robert D. Skeel,*Scaling for numerical stability in Gaussian elimination*, J. Assoc. Comput. Mach.**26**(1979), no. 3, 494–526. MR**535268**, 10.1145/322139.322148**15.**G. W. Stewart,*On the perturbation of pseudo-inverses, projections and linear least squares problems*, SIAM Rev.**19**(1977), no. 4, 634–662. MR**0461871****16.**G. W. Stewart and Ji Guang Sun,*Matrix perturbation theory*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR**1061154****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

Retrieve articles in all journals with MSC (2000): 15A09, 15A12, 65F35

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

DOI:
https://doi.org/10.1090/S0025-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

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.

Article copyright:
© Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.