Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

Equivalent formulae for the supremum and stability of weighted pseudoinverses

Author(s): Musheng Wei.
Journal: Math. Comp. 66 (1997), 1487-1508.
MSC (1991): Primary 15A09, 65F35
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

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 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: 10.1090/S0025-5718-97-00899-5
PII: S 0025-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
Copyright of article: Copyright 1997, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google