Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $\underset {W\in \mathcal {P} }{\text {sup}}\|(W^{\frac {1}{2}}X)^{+}W^{\frac {1}{2}}\|_{2}$ of a matrix $X$ where $\mathcal {P}$ 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 $\underset {W\in \mathcal {P} }{\text {sup}}\|(W^{\frac {1}{2}}X)^{+}W^{\frac {1}{2}}\|_{2}$ where $\mathcal {P}$ is a set of diagonally dominant positive semidefinite matrices, by using a signature decomposition of weighting matrices $W$ 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 $X$ to establish several equivalent formulae for $\underset {W\in \mathcal {P} }{\text {sup}}\|(W^{\frac {1}{2}}X)^{+}W^{\frac {1}{2}}\|_{2}$, where $\mathcal {P}$ 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.


References [Enhancements On Off] (What's this?)

  • 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.

Similar Articles

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

American Mathematical Society