Equivalent formulae for the supremum and stability of weighted pseudoinverses

Author:
Musheng Wei

Journal:
Math. Comp. **66** (1997), 1487-1508

MSC (1991):
Primary 15A09, 65F35

DOI:
https://doi.org/10.1090/S0025-5718-97-00899-5

MathSciNet review:
1433270

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: During recent decades, there have been a great number of research articles studying interior-point methods for solving problems in mathematical programming and constrained optimization. Stewart and O'Leary obtained an upper bound for scaled pseudoinverses of a matrix where is a set of diagonal positive definite matrices. We improved their results to obtain the supremum of scaled pseudoinverses and derived the stability property of scaled pseudoinverses. Forsgren further generalized these results to derive the supremum of weighted pseudoinverses where is a set of diagonally dominant positive semidefinite matrices, by using a signature decomposition of weighting matrices and by applying the Binet-Cauchy formula and Cramer's rule for determinants. The results are also extended to equality constrained linear least squares problems. In this paper we extend Forsgren's results to a general complex matrix to establish several equivalent formulae for , where is a set of diagonally dominant positive semidefinite matrices, or a set of weighting matrices arising from solving equality constrained least squares problems. We also discuss the stability property of these weighted pseudoinverses.

**1.**A. Ben-Israel and T.N.E. Greville,*Generalized Inverses: Theory and Applications*, John Wiley, New York, 1974.MR**81h:15005****2.**A. Ben-Tal and M. Teboulle,*A geometric property of the least squares solution of linear equations*, Linear Algebra Appl.**139**(1990), 165-170.MR**91h:15004****3.**I.I. Dikin,*On the speed of an iterative process*, Upravlyaemye Sistemi**12**(1974), 54-60.**4.**A. Forsgren,*On linear least-squares problems with diagonally dominant weight matrices*, SIAM J. Matrix Anal. Appl.**17**(1996), 763-788. CMP**97:01****5.**A. Forsgren, P.E. Gill and J.R. Shinnerl,*Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization*, SIAM J. Matrix Anal. Appl.**17**(1996), 187-211.MR**96m:90084****6.**P.E. Gill, W. Murray and M.H. Wright,*Numerical Linear Algebra and Optimization, Vol. 1*, Addison-Wesley Publishing Company, Redwood City, 1991.MR**92b:65001****7.**G.H. Golub and C.F. Van Loan,*Matrix Computations*, 2nd Edit., The Johns Hopkins University Press, Baltimore, MD, 1989. MR**90d:65055****8.**C.C. Gonzaga,*Path-following methods for linear programming*, SIAM Review**34**(1992), 167-224. MR**93j:90050****9.**M. Gullikson and P.-Å. Wedin,*Modifying the QR decomposition to constrained and weighted linear least squares*, SIAM J. Matrix Anal. Appl.**13**(1992), 1298-1313. MR**93e:65066****10.**M.Hanke and M. Neumann,*The geometry of the set of scaled projections*, Linear Algebra Appl.**190**(1993), 137-148.MR**94g:15002****11.**R.A. Horn and C.R. Johnson,*Matrix Analysis*, Cambridge University Press, Cambridge, UK, 1985. MR**87e:15001****12.**D. P. O'Leary,*On bounds for scaled projections and pseudoinverses*, Linear Algebra Appl.**132**(1990), 115-117. MR**91f:15056****13.**J. Miao and A. Ben-Israel,*The geometry of basic, approximate, and minimum- norm solution of linear equations*, Linear Algebra Appl.**216**(1995), 25-41.MR**96e:15003****14.**C.C. Paige and M.A. Saunders,*Towards a generalized singular value decomposition*, SIAM J. Numer. Anal.**18**(1981), 398-405. MR**83c:65082****15.**G.W. Stewart,*On scaled projections and pseudoinverses*, Linear Algebra Appl.**112**(1989), 189-193.MR**90d:15005****16.**G.W. Stewart and J.-G. Sun,*Matrix Perturbation Theory*, Academic Press, New York, 1990.MR**92a:65017****17.**R.J. Vanderbei and J.C. Lagarias,*Dikin's convergence result for the affine-scaling algorithm*, Contemporary Mathematics**114**(1990), 109-119. MR**92d:90046****18.**S.A. Vavasis,*Stable numerical algorithms for equilibrium system*, SIAM J. Matrix Anal. Appl.**15**(1994), 1108-1131. MR**95m:65080****19.**M. Wei,*Algebraic properties of the rank- deficient equality constrained and weighted least squares problems*, Linear Algebra Appl.**161**(1992), 27-43.MR**92j:65059****20.**M. Wei,*Perturbation theory for the rank- deficient equality constrained least squares problem*, SIAM J. Numer. Anal.**29**(1992), 1462-1481. MR**93i:65046****21.**M.Wei,*Upper bound and stability of scaled pseudoinverses*, Numer. Math.**72**(1995), 285-293.MR**96k:65031****22.**M.H. Wright,*Interior methods for constrained optimization*, In A. Iserles, edit., Acta Numerica, pp.341-407, Cambridge University Press, Cambridge, UK, 1992. MR**93d:90037****23.**S. Wright,*Stability of linear equations solvers in interior-point methods*, SIAM J. Matrix Anal. Appl.**16**(1995), 1287-1307. MR**96f:65055****24.**S. Wright,*Stability of linear algebra computations in interior-point methods for linear programming*, Tech. Rep. MCS- P400- 1293, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 1993.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
15A09,
65F35

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

Additional Information

**Musheng Wei**

Affiliation:
Department of Mathematics, East China Normal University, Shanghai 200062, China

DOI:
https://doi.org/10.1090/S0025-5718-97-00899-5

Keywords:
Weighted pseudoinverse,
supremum,
stability

Received by editor(s):
March 27, 1996

Additional Notes:
This work was supported by the National Natural Science Foundation, P.R. China

Article copyright:
© Copyright 1997
American Mathematical Society