×

Conjugate gradient method for computing the Moore-Penrose inverse and rank of a matrix. (English) Zbl 0336.65023

Summary: A conjugate-gradient method is developed for computing the Moore-Penrose generalized inverse \(A^\dagger\) of a matrix and the associated projectors, by using the least-square characteristics of both the method and the inverse \(A^\dagger\) . Two dual algorithms are introduced for computing the least-square and the minimum-norm generalized inverses, as well as \(A^\dagger\). It is shown that (i) these algorithms converge for any starting approximation; (ii) if they are started from the zero matrix, they converge to \(A^\dagger\); and (iii) the trace of a sequence of approximations multiplied by \(A\) is a monotone increasing function converging to the rank of \(A\). A practical way of compensating the self-correcting feature in the computation of \(A^\dagger\) is devised by using the duality of the algorithms. Comparison with Ben-Israel’s method is made through numerical examples. The conjugate-gradient method has an advantage over Ben-Israel’s method.
{After having completed the present paper, the author received from Professor M. R. Hestenes his paper entitled “Pseudo lnverses and Conjugate Gradients”. This paper treated the same subject and appeared in Commun. ACM 18, 40–43 (1975; Zbl 0304.65029).}

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A09 Theory of matrix inversion and generalized inverses

Citations:

Zbl 0304.65029
Full Text: DOI

References:

[1] Ben-Israel, A., andWersan, S. J.,An Elimination Method for Computing the Generalized Inverse of an Arbitrary Complex Matrix, Journal of the Association for Computing Machinery, Vol. 10, pp. 532-537, 1963. · Zbl 0118.12104
[2] Boot, J. C. G.,The Computation of the Generalized Inverse of Singular or Rectangular Matrices, American Mathematical Monthly, Vol. 70, pp. 302-303, 1963. · Zbl 0112.01203 · doi:10.2307/2313135
[3] Germain-Bonne, G., Calcul de Pseudo-Inverses, Revue Française d’Automatique, Informatique et Recherche Operationnelle, Vol. 3, pp. 3-14, 1969. · Zbl 0193.11803
[4] Glassey, C. R.,An Orthogonalization Method of Computing the Generalized Inverse of a Matrix, University of California, Berkeley, Operations Research Center, Report No. ORC-66-10, 1966.
[5] Golub, G. H., andKahan, W.,Calculating the Singular Values and Pseudo-Inverse of a Matrix, SIAM Journal on Numerical Analysis, Vol. 2, pp. 205-224, 1965. · Zbl 0194.18201
[6] Golub, G. H., andReinsch, C.,Singular Value Decomposition and Least Squares Solution, Numerische Mathematik, Vol. 14, pp. 403-420, 1970. · Zbl 0181.17602 · doi:10.1007/BF02163027
[7] Greville, T. N. E.,The Pseudo-Inverse of a Rectangular or Singular Matrix and Its Applications to the Solution of Lienar Equations, SIAM Review, Vol. 1, pp. 38-43, 1959. · Zbl 0123.11202 · doi:10.1137/1001003
[8] Kublanovskaya, V. N.,Evaluation of a Generalized Inverse Matrix and Projector, USSR Computational Mathematics and Mathematical Physics, Vol. 6, pp. 179-188, 1966. · Zbl 0171.35904 · doi:10.1016/0041-5553(66)90064-4
[9] Mayne, D.,An Algorithm for the Calculation of the Pseudo-Inverse of a Singular Matrix, Computer Journal, Vol. 9, pp. 312-317, 1966. · Zbl 0152.35401
[10] Noble, G.,A Method for Computing the Generalized Inverse of a Matrix, SIAM Journal on Numerical Analysis, Vol. 3, pp. 582-584, 1966. · Zbl 0147.13105 · doi:10.1137/0703049
[11] Peters, G., andWilkinson, J. H.,The Least Squares Problem and Pseudo-Inverses, Computer Journal, Vol. 13, pp. 309-316, 1970. · Zbl 0195.44804 · doi:10.1093/comjnl/13.3.309
[12] Pyle, L. D.,Generalized Inverse Computations Using the Gradient Projection Method, Journal of the Association for Computing Machinery, Vol. 11, pp. 422-428, 1964. · Zbl 0123.11203
[13] Rust, B., Burrus, W. R., andSchneeberger, C.,A Simple Algorithm for Computing the Generalized Inverse of a Matrix, Communications of the Association for Computing Machinery, Vol. 9, pp. 381-387, 1966. · Zbl 0135.37401
[14] Shinozaki, N., Sibuya, M., andTanabe, K.,Numerical Algorithms for the Moore-Penrose Inverse of a Matrix: Direct Methods, Annals of the Institute of Statistical Mathematics, Vol. 24, pp. 193-203, 1972. · Zbl 0315.65027 · doi:10.1007/BF02479751
[15] Tewarson, R. P.,A Direct Method for Generalized Matrix Inversion, SIAM Journal on Numerical Analysis, Vol. 4, pp. 499-507, 1967. · Zbl 0153.46102 · doi:10.1137/0704045
[16] Tewarson, R. P.,A Computational Method for Evaluation of Generalized Inverses, Computer Journal, Vol. 10, pp. 411-413, 1968. · Zbl 0167.15602 · doi:10.1093/comjnl/10.4.411
[17] Tewarson, R. P.,On Computing Generalized Inverses, Computing, Vol. 4, pp. 139-151, 1969. · Zbl 0182.21203 · doi:10.1007/BF02234761
[18] Tewarson, R. P.,On Two Direct Methods for Computing Generalized Inverses, Computing, Vol. 7, pp. 236-239, 1971. · Zbl 0222.65049 · doi:10.1007/BF02242350
[19] Willner, L. B.,An Elimination Method for Computing the Generalized Inverse, Mathematics of Computation, Vol. 21, pp. 227-229, 1967. · Zbl 0166.41601 · doi:10.1090/S0025-5718-1967-0223082-8
[20] Ben-Israel, A.,An Iterative Method for Computing the Generalized Inverse of an Arbitrary Matrix, Mathematics of Computation, Vol. 19, pp. 452-455, 1965. · Zbl 0136.12703 · doi:10.1090/S0025-5718-1965-0179915-5
[21] Ben-Israel, A.,A Note on an Iterative Method for Generalized Inversion of Matrices, Mathematics of Computation, Vol. 20, pp. 439-440, 1966. · Zbl 0142.11603 · doi:10.1090/S0025-5718-66-99922-4
[22] Ben-Israel, A., andCohen, D.,On Iterative Computation of Generalized Inverses and Associated Projections, SIAM Journal on Numerical Analysis, Vol. 3, pp. 410-419, 1966. · Zbl 0143.37402 · doi:10.1137/0703035
[23] Garnett, J. M., Ben-Israel, A., andYau, S. S.,A Hyperpower Iterative Method for Computing Matrix Products Involving the Generalized Inverse, SIAM Journal on Numerical Analysis, Vol. 8, pp. 104-109, 1971. · Zbl 0217.52605 · doi:10.1137/0708013
[24] Petryshyn, W. V.,On Generalized Inverses and on Uniform Convergence of)n with Application to Iterative Methods,Journal of Mathematical Analysis and Applications, Vol. 18, pp. 417-439, 1967. · Zbl 0189.47502 · doi:10.1016/0022-247X(67)90036-4
[25] Shinozaki, N., Sibuya, M., andTanabe, K.,Numerical Algorithms for the Moore-Penrose Inverse of a Matrix: Iterative Methods, Annals of the Institute of Statistical Mathematics, Vol. 24, pp. 621-629, 1972. · Zbl 0314.65016 · doi:10.1007/BF02479787
[26] Tanabe, K.,Neumann-Type Expansion of Reflexive Generalized Inverses of a Matrix and the Hyperpower Iterative Method, Linear Algebra and Its Applications, Vol. 10, pp. 163-175, 1975. · Zbl 0327.15012 · doi:10.1016/0024-3795(75)90008-7
[27] Söderström, T., andStewart, G. W.,On the Numerical Properties of an Iterative Method for Computing the Moore-Penrose Generalized Inverse, SIAM Journal on Numerical Analysis, Vol. 11, pp. 61-74, 1974. · doi:10.1137/0711008
[28] Zlobec, S.,On Computing the Generalized Inverse of a Linear Operator, Glasnik Matematicki, Vol. 2, pp. 265-271, 1967. · Zbl 0149.35101
[29] Zlobec, S., andBen-Israel, A.,On K u-Symmetric and Ku-pd Matrices with Applications to Hyperpower Methods of Generalized Inversion, Northwestern University, Evanston, Illinois, Systems Research Memorandum, No. 214, 1968.
[30] Tewarson, R. P.,An Iterative Method for Computing Generalized Inverses, International Journal of Computer Mathematics, Vol. 3, pp. 65-74, 1971. · Zbl 0227.65028 · doi:10.1080/00207167108803052
[31] Decell, H. P.,An Application of the Cayley-Hamilton Theory to Generalized Matrix Inversion, SIAM Review, Vol. 7, pp. 526-528, 1965. · Zbl 0178.35504 · doi:10.1137/1007108
[32] Stallings, W. T., andBoullion, T. L.,Computation of Pseudo-Inverse Matrices Using Residue Arithmetic, SIAM Review, Vol. 14, pp. 152-163, 1972. · Zbl 0238.65016 · doi:10.1137/1014005
[33] Penrose, R.,On Best Approximate Solutions of Linear Matrix Equations, Proceedings of the Cambridge Philosophical Society, Vol. 52, pp. 17-19, 1956. · Zbl 0070.12501 · doi:10.1017/S0305004100030929
[34] Reid, J. K.,On the Method of Conjugate Gradients for the Solution of Large Sparse Systems of Linear Equations, Proceedings of the Conference on Large Sparse Sets of Linear Equations, Edited by J. K. Reid, Academic Press, New York, New York, 1971. · Zbl 0229.65032
[35] Reid, J. K.,The Use of Conjugate Gradients for Systems of Linear Equations Possessing Property A, SIAM Journal on Numerical Analysis, Vol. 9, pp. 325-332, 1972. · Zbl 0259.65037 · doi:10.1137/0709032
[36] Kammerer, W. J., andNashed, M. Z.,On the Convergence of the Conjugate Gradient Method for Singular Linear Operator Equations, SIAM Journal on Numerical Analysis, Vol. 9, pp. 165-181, 1972. · Zbl 0243.65026 · doi:10.1137/0709016
[37] Hestenes, M. R., andStiefel, E.,Method of Conjugate Gradients for Solving Linear Systems, Journal of Research of the National Bureau of Standards, Vol. 49, pp. 409-436, 1952. · Zbl 0048.09901
[38] Hestenes, M. R.,The Conjugate Gradient Method for Solving Linear Systems, Proceedings of the Symposia on Applied Mathematics VI, Edited by J. H. Curtis, American Mathematical Society, Providence, Rhode Island, pp. 83-102, 1956. · Zbl 0072.14102
[39] Hestenes, M. R.,Iterative Methods for Solving Linear Equations, Journal of Optimization Theory and Applications, Vol. 11, pp. 323-334, 1973. · doi:10.1007/BF00932484
[40] Stiefel, E. L.,Kernel Polynomials in Linear Algebra and Their Numerical Applications, National Bureau of Standards, Applied Mathematics Series, No. 49, 1958. · Zbl 0171.35703
[41] Varah, J. M.,On the Numerical Solution of Ill-Conditioned Linear Systems with Applications to Ill-Posed Problems, SIAM Journal on Numerical Analysis, Vol. 10, pp. 257-267, 1973. · Zbl 0261.65034 · doi:10.1137/0710025
[42] Forsythe, G. E.,On the Asymptotic Directions of the s-Dimensional Optimum Gradient Method, Numerische Mathematik, Vol. 11, pp. 57-76, 1968. · Zbl 0153.46004 · doi:10.1007/BF02165472
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.