On mixed and componentwise condition numbers for MoorePenrose inverse and linear least squares problems
Authors:
Felipe Cucker, Huaian Diao and Yimin Wei
Journal:
Math. Comp. 76 (2007), 947963
MSC (2000):
Primary 15A09, 15A12; Secondary 65F35
Published electronically:
November 2, 2006
MathSciNet review:
2291844
Fulltext 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 MoorePenrose 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
leastsquares problems, Numer. Math. 55 (1989),
no. 6, 667–684. MR 1005065
(90g:65048), http://dx.doi.org/10.1007/BF01389335
 2.
Adi
BenIsrael and Thomas
N. E. Greville, Generalized inverses, 2nd ed., CMS Books in
Mathematics/Ouvrages de Mathématiques de la SMC, 15,
SpringerVerlag, New York, 2003. Theory and applications. MR 1987382
(2004b:15008)
 3.
Å.
Björck, Componentwise perturbation analysis and error bounds
for linear least squares solutions, BIT 31 (1991),
no. 2, 238–244. MR 1112220
(92i:65079), http://dx.doi.org/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
(94c:65050), http://dx.doi.org/10.1137/0614001
 5.
A.
J. Geurts, A contribution to the theory of condition, Numer.
Math. 39 (1982), no. 1, 85–96. MR 664538
(83g:65046), http://dx.doi.org/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
(94j:65062), http://dx.doi.org/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
(83g:15001)
 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 (97h:65050), http://dx.doi.org/10.1007/BF01731931
 9.
J.F. Grcar, Optimal sensitivity analysis of linear least squares, Lawrence Berkeley National Laboratory, Report LBNL52434, 2003.
 10.
Nicholas
J. Higham, A survey of componentwise perturbation theory in
numerical linear algebra, Mathematics of Computation 1943–1993:
a halfcentury of computational mathematics (Vancouver, BC, 1993) Proc.
Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994,
pp. 49–77. MR 1314843
(96a:65065), http://dx.doi.org/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 (2004f:65052), http://dx.doi.org/10.1137/S0895479801389564
 12.
John
R. Rice, A theory of condition, SIAM J. Numer. Anal.
3 (1966), 287–310. MR 0211576
(35 #2454)
 13.
J.
Rohn, New condition numbers for matrices and linear systems,
Computing 41 (1989), no. 12, 167–169 (English,
with German summary). MR 981682
(90a:65104), http://dx.doi.org/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
(80e:65051), http://dx.doi.org/10.1145/322139.322148
 15.
G.
W. Stewart, On the perturbation of pseudoinverses, projections and
linear least squares problems, SIAM Rev. 19 (1977),
no. 4, 634–662. MR 0461871
(57 #1854)
 16.
G.
W. Stewart and Ji
Guang Sun, Matrix perturbation theory, Computer Science and
Scientific Computing, Academic Press, Inc., Boston, MA, 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 pseudoinverses, BIT, 13(1973), pp. 217232.
 1.
 M. Arioli, I.S. Duff and P.P.M. de Rijk, An augmented system approach to sparse leastsquares problems, Numer. Math. 55(1989), pp. 667684. MR 1005065 (90g:65048)
 2.
 A. BenIsrael and T.N.E. Greville, Generalized Inverses: Theory and Applications, 2nd Edition, Springer Verlag, New York, 2003. MR 1987382 (2004b:15008)
 3.
 Å. Björck, Componentwise perturbation analysis and error bounds for linear least squares solutions, BIT, 31(1991), pp. 238244. 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. 114. MR 1199540 (94c:65050)
 5.
 A.J. Geurts, A Contribution to the theory of condition, Numer. Math., 39(1982), pp. 8596. MR 0664538 (83g:65046)
 6.
 I. Gohberg and I. Koltracht, Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl., 14(1993), pp. 688704. 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. 523530. MR 1410095 (97h:65050)
 9.
 J.F. Grcar, Optimal sensitivity analysis of linear least squares, Lawrence Berkeley National Laboratory, Report LBNL52434, 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. 4977. 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. 11861196. MR 2003329 (2004f:65052)
 12.
 J.R. Rice, A theory of condition, SIAM J. Numer. Anal., 3(1966), pp. 217232. MR 0211576 (35:2454)
 13.
 J. Rohn, New condition numbers for matrices and linear systems, Computing, 41(1989), pp. 167169. MR 0981682 (90a:65104)
 14.
 R.D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26(1979), No.3, pp. 817526. MR 0535268 (80e:65051)
 15.
 G.W. Stewart, On the perturbation of pseudoinverses, projections and linear least sqaures problems, SIAM Rev., 19 (1977), pp. 634662. 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 pseudoinverses, BIT, 13(1973), pp. 217232.
Similar Articles
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:
http://dx.doi.org/10.1090/S0025571806019132
PII:
S 00255718(06)019132
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.
