Geodesic
Convergence of Rump's method for computing the Moore-Penrose inverse
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 859-879
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

We extend Rump's verified method (S. Oishi, K. Tanabe, T. Ogita, S. M. Rump (2007)) for computing the inverse of extremely ill-conditioned square matrices to computing the Moore-Penrose inverse of extremely ill-conditioned rectangular matrices with full column (row) rank. We establish the convergence of our numerical verified method for computing the Moore-Penrose inverse. We also discuss the rank-deficient case and test some ill-conditioned examples. We provide our Matlab codes for computing the Moore-Penrose inverse.
We extend Rump's verified method (S. Oishi, K. Tanabe, T. Ogita, S. M. Rump (2007)) for computing the inverse of extremely ill-conditioned square matrices to computing the Moore-Penrose inverse of extremely ill-conditioned rectangular matrices with full column (row) rank. We establish the convergence of our numerical verified method for computing the Moore-Penrose inverse. We also discuss the rank-deficient case and test some ill-conditioned examples. We provide our Matlab codes for computing the Moore-Penrose inverse.
DOI : 10.1007/s10587-016-0297-3
Classification : 15A24, 65F05
Keywords: Moore-Penrose inverse; condition number; ill-conditioned matrix 
@article{10_1007_s10587_016_0297_3,
     author = {Chen, Yunkun and Shi, Xinghua and Wei, Yimin},
     title = {Convergence of {Rump's} method for computing the {Moore-Penrose} inverse},
     journal = {Czechoslovak Mathematical Journal},
     pages = {859--879},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0297-3},
     mrnumber = {3556872},
     zbl = {06644038},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0297-3/}
}
TY  - JOUR
AU  - Chen, Yunkun
AU  - Shi, Xinghua
AU  - Wei, Yimin
TI  - Convergence of Rump's method for computing the Moore-Penrose inverse
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 859
EP  - 879
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0297-3/
DO  - 10.1007/s10587-016-0297-3
LA  - en
ID  - 10_1007_s10587_016_0297_3
ER  - 
%0 Journal Article
%A Chen, Yunkun
%A Shi, Xinghua
%A Wei, Yimin
%T Convergence of Rump's method for computing the Moore-Penrose inverse
%J Czechoslovak Mathematical Journal
%D 2016
%P 859-879
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0297-3/
%R 10.1007/s10587-016-0297-3
%G en
%F 10_1007_s10587_016_0297_3
Chen, Yunkun; Shi, Xinghua; Wei, Yimin. Convergence of Rump's method for computing the Moore-Penrose inverse. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 859-879. doi: 10.1007/s10587-016-0297-3

[1] Ben-Israel, A., Greville, T. N. E.: Generalized Inverses. Theory and Applications. Springer, New York (2003). | MR | Zbl

[2] Björck, Å.: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics (SIAM) Philadelphia (1996). | MR | Zbl

[3] Campbell, S. L., Meyer, C. D.: Generalized Inverses of Linear Transformations. Dover Publications, New York (1991). | MR | Zbl

[4] Castro-González, N., Ceballos, J., Dopico, F. M., Molera, J. M.: Accurate solution of structured least squares problems via rank-revealing decompositions. SIAM J. Matrix Anal. Appl. 34 (2013), 1112-1128. | DOI | MR | Zbl

[5] Chen, L., Krishnamurthy, E. V., Madeod, I.: Generalised matrix inversion and rank computation by successive matrix powering. Parallel Comput. 20 (1994), 297-311. | DOI | MR

[6] Courrieu, P.: Fast computation of Moore-Penrose inverse matrices. Neural Information Processing 8 (2005), 25-29.

[7] Cucker, F., Diao, H., Wei, Y.: On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems. Math. Comput. 76 (2007), 947-963. | DOI | MR | Zbl

[8] Cucker, F., Diao, H., Wei, Y.: Smoothed analysis of some condition numbers. Numer. Linear Algebra Appl. 13 (2006), 71-84. | DOI | MR | Zbl

[9] Demmel, J., Gu, M., Eisenstat, S., Slapničar, I., Veselić, K., Drmač, Z.: Computing the singular value decomposition with high relative accuracy. Linear Algebra Appl. 299 (1999), 21-80. | MR | Zbl

[10] Demmel, J. W., Hida, Y., Li, X. S., Riedy, E. J.: Extra-precise iterative refinement for overdetermined least squares problems. ACM Trans. Math. Software 35 (2009), Art. 28, 32 pages. | DOI | MR

[11] Demmel, J., Higham, N. J.: Improved error bounds for underdetermined system solvers. SIAM J. Matrix Anal. Appl. 14 (1993), 1-14. | DOI | MR

[12] Diao, H., Wei, Y.: On Frobenius normwise condition numbers for Moore-Penrose inverse and linear least-squares problems. Numer. Linear Algebra Appl. 14 (2007), 603-610. | DOI | MR | Zbl

[13] Diao, H., Wei, Y., Qiao, S.: Structured condition numbers of structured Tikhonov regularization problem and their estimations. J. Comput. Appl. Math. 308 (2016), 276-300. | DOI | MR | Zbl

[14] Dopico, F. M., Molera, J. M.: Accurate solution of structured linear systems via rank-revealing decompositions. IMA J. Numer. Anal. 32 (2012), 1096-1116. | DOI | MR | Zbl

[15] Fiedler, M.: Moore-Penrose biorthogonal systems in Euclidean spaces. Linear Algebra Appl. 362 (2003), 137-143. | DOI | MR | Zbl

[16] Fiedler, M., Markham, T. L.: A characterization of the Moore-Penrose inverse. Linear Algebra Appl. 179 (1993), 129-133. | MR | Zbl

[17] Golub, G. H., Loan, C. F. Van: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences Johns Hopkins University Press, Baltimore (2013). | MR

[18] Gulliksson, M., Wedin, P. Å., Wei, Y.: Perturbation identities for regularized Tikhonov inverses and weighted pseudoinverses. BIT 40 (2000), 513-523. | DOI | MR

[19] Jones, J., Karampetakis, N. P., Pugh, A. C.: The computation and application of the generalized inverse via Maple. J. Symb. Comput. 25 (1998), 99-124. | DOI | MR | Zbl

[20] Katsikis, V. N., Pappas, D.: Fast computing of the Moore-Penrose inverse matrix. Electron. J. Linear Algebra (electronic only) 17 (2008), 637-650. | MR | Zbl

[21] Li, Z.-C., Huang, H.-T., Wei, Y., Cheng, A. H.-D.: Effective Condition Number for Numerical Partial Differential Equations. Alpha Science International, Oxford (2014). | MR

[22] Li, Z., Xu, Q., Wei, Y.: A note on stable perturbations of Moore-Penrose inverses. Numer. Linear Algebra Appl. 20 (2013), 18-26. | DOI | MR | Zbl

[23] Ogita, T., Rump, S. M., Oishi, S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26 (2005), 1955-1988. | DOI | MR | Zbl

[24] Ohta, T., Ogita, T., Rump, S. M., Oishi, S.: Numerical verification method for arbitrarily ill-conditioned linear systems. Transactions of the Japan Society for Industrial and Applied Mathematics 15 (2005), 269-287.

[25] Oishi, S., Rump, S. M.: Fast verification of solutions of matrix equations. Numer. Math. 90 (2002), 755-773. | DOI | MR | Zbl

[26] Oishi, S., Tanabe, K., Ogita, T., Rump, S. M.: Convergence of Rump's method for inverting arbitrarily ill-conditioned matrices. J. Comput. Appl. Math. 205 (2007), 533-544. | DOI | MR | Zbl

[27] Rao, C. R., Mitra, S. K.: Generalized Inverses of Matrices and Its Applications. Wiley Series in Probability and Mathematical Statistics Wiley & Sons, New York (1971). | MR

[28] Rump, S. M.: Verified bounds for least squares problems and underdetermined linear systems. SIAM J. Matrix Anal. Appl. 33 (2012), 130-148. | DOI | MR | Zbl

[29] Rump, S. M.: Inversion of extremely ill-conditioned matrices in floating-point. Japan J. Ind. Appl. Math. 26 (2009), 249-277. | DOI | MR | Zbl

[30] Rump, S. M.: INTLAB---Interval Laboratory, the Matlab toolbox for verified computations, Version 5.3. Institute for Reliable Computing, Hamburg (2006).

[31] Rump, S. M.: Ill-conditioned matrices are componentwise near to singularity. SIAM Rev. 41 (1999), 102-112. | DOI | MR | Zbl

[32] Rump, S. M.: Ill-conditionedness need not be componentwise near to ill-posedness for least squares problems. BIT 39 (1999), 143-151. | DOI | MR | Zbl

[33] Rump, S. M.: A class of arbitrarily ill-conditioned floating-point matrices. SIAM J. Matrix Anal. Appl. 12 (1991), 645-653. | DOI | MR | Zbl

[34] Rump, S. M.: Approximate Inverses of Almost Singular Matrices Still Contain Useful Information, Technical Report 90.1. Faculty for Information and Communications Sciences, TU Hamburg Harburg (1990).

[35] Smoktunowicz, A., Barlow, J., Langou, J.: A note on the error analysis of classical Gram-Schmidt. Numer. Math. 105 (2006), 299-313. | DOI | MR | Zbl

[36] Smoktunowicz, A., Wróbel, I.: Numerical aspects of computing the Moore-Penrose inverse of full column rank matrices. BIT 52 (2012), 503-524. | DOI | MR | Zbl

[37] Stewart, G. W.: On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Rev. 19 (1977), 634-662. | DOI | MR

[38] Wang, G., Wei, Y., Qiao, S.: Generalized Inverses: Theory and Computations. Science Press, Beijing (2004). | MR

[39] Wedin, P. Å.: Perturbation theory for pseudo-inverses. BIT, Nord. Tidskr. Inf.-behandl. 13 (1973), 217-232. | MR | Zbl

[40] Wei, Y.: Generalized inverses of matrices, Chapter 27. Handbook of Linear Algebra L. Hogben Chapman & Hall/CRC Press, Boca Raton (2014), 27-1-27-15. | MR

[41] Wei, Y., Ding, J.: Representations for Moore-Penrose inverses in Hilbert spaces. Appl. Math. Lett. 14 (2001), 599-604. | DOI | MR | Zbl

[42] Wei, Y., Wu, H.: Expression for the perturbation of the weighted Moore-Penrose inverse. Comput. Math. Appl. 39 (2000), 13-18. | DOI | MR | Zbl

[43] Wei, Y., Xie, P., Zhang, L.: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37 (2016), 649-675. | DOI | MR | Zbl

[44] Xu, W., Wei, Y., Qiao, S.: Condition numbers for structured least squares problems. BIT 46 (2006), 203-225. | DOI | MR | Zbl

[45] Zhou, L., Lin, L., Wei, Y., Qiao, S.: Perturbation analysis and condition numbers of scaled total least squares problems. Numer. Algorithms 51 (2009), 381-399. | DOI | MR | Zbl

[46] Zielke, G.: Report on test matrices for generalized inverses. Computing 36 (1986), 105-162. | DOI | MR | Zbl

Cité par Sources :