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 Free Access

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.

- Adi Ben-Israel and Thomas N. E. Greville,
*Generalized inverses: theory and applications*, Robert E. Krieger Publishing Co., Inc., Huntington, N.Y., 1980. Corrected reprint of the 1974 original. MR**587113** - Aharon Ben-Tal and Marc Teboulle,
*A geometric property of the least squares solution of linear equations*, Linear Algebra Appl.**139**(1990), 165–170. MR**1071706**, DOI https://doi.org/10.1016/0024-3795%2890%2990395-S - I.I. Dikin,
*On the speed of an iterative process*, Upravlyaemye Sistemi**12**(1974), 54-60. - A. Forsgren,
*On linear least-squares problems with diagonally dominant weight matrices*, SIAM J. Matrix Anal. Appl.**17**(1996), 763–788. - Anders Forsgren, Philip E. Gill, and Joseph R. Shinnerl,
*Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization*, SIAM J. Matrix Anal. Appl.**17**(1996), no. 1, 187–211. MR**1372930**, DOI https://doi.org/10.1137/S0895479894270658 - Philip E. Gill, Walter Murray, and Margaret H. Wright,
*Numerical linear algebra and optimization. Vol. 1*, Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1991. MR**1074004** - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR**1002570** - Clovis C. Gonzaga,
*Path-following methods for linear programming*, SIAM Rev.**34**(1992), no. 2, 167–224. MR**1166175**, DOI https://doi.org/10.1137/1034048 - Mårten Gulliksson and Per-Åke Wedin,
*Modifying the $QR$-decomposition to constrained and weighted linear least squares*, SIAM J. Matrix Anal. Appl.**13**(1992), no. 4, 1298–1313. MR**1182728**, DOI https://doi.org/10.1137/0613079 - Martin Hanke and Michael Neumann,
*The geometry of the set of scaled projections*, Linear Algebra Appl.**190**(1993), 137–148. MR**1230355**, DOI https://doi.org/10.1016/0024-3795%2893%2990223-B - Roger A. Horn and Charles R. Johnson,
*Matrix analysis*, Cambridge University Press, Cambridge, 1985. MR**832183** - Dianne P. O’Leary,
*On bounds for scaled projections and pseudoinverses*, Linear Algebra Appl.**132**(1990), 115–117. MR**1058094**, DOI https://doi.org/10.1016/0024-3795%2890%2990056-I - Jian Ming Miao and Adi Ben-Israel,
*The geometry of basic, approximate, and minimum-norm solutions of linear equations*, Linear Algebra Appl.**216**(1995), 25–41. MR**1319973**, DOI https://doi.org/10.1016/0024-3795%2893%2900093-F - C. C. Paige and M. A. Saunders,
*Towards a generalized singular value decomposition*, SIAM J. Numer. Anal.**18**(1981), no. 3, 398–405. MR**615522**, DOI https://doi.org/10.1137/0718026 - G. W. Stewart,
*On scaled projections and pseudoinverses*, Linear Algebra Appl.**112**(1989), 189–193. MR**976336**, DOI https://doi.org/10.1016/0024-3795%2889%2990594-6 - G. W. Stewart and Ji Guang Sun,
*Matrix perturbation theory*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR**1061154** - R. J. Vanderbei and J. C. Lagarias,
*I. I. Dikin’s convergence result for the affine-scaling algorithm*, Mathematical developments arising from linear programming (Brunswick, ME, 1988) Contemp. Math., vol. 114, Amer. Math. Soc., Providence, RI, 1990, pp. 109–119. MR**1097868**, DOI https://doi.org/10.1090/conm/114/1097868 - Stephen A. Vavasis,
*Stable numerical algorithms for equilibrium systems*, SIAM J. Matrix Anal. Appl.**15**(1994), no. 4, 1108–1131. MR**1293907**, DOI https://doi.org/10.1137/S0895479892230948 - Mu Sheng Wei,
*Algebraic properties of the rank-deficient equality-constrained and weighted least squares problems*, Linear Algebra Appl.**161**(1992), 27–43. MR**1142728**, DOI https://doi.org/10.1016/0024-3795%2892%2990003-S - Mu Sheng Wei,
*Perturbation theory for the rank-deficient equality constrained least squares problem*, SIAM J. Numer. Anal.**29**(1992), no. 5, 1462–1481. MR**1182740**, DOI https://doi.org/10.1137/0729084 - Mu Sheng Wei,
*Upper bound and stability of scaled pseudoinverses*, Numer. Math.**72**(1995), no. 2, 285–293. MR**1362264**, DOI https://doi.org/10.1007/s002110050170 - Margaret H. Wright,
*Interior methods for constrained optimization*, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 341–407. MR**1165729**, DOI https://doi.org/10.1017/s0962492900002300 - Stephen J. Wright,
*Stability of linear equations solvers in interior-point methods*, SIAM J. Matrix Anal. Appl.**16**(1995), no. 4, 1287–1307. MR**1351471**, DOI https://doi.org/10.1137/S0895479893260498 - 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*
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

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