| Title:
|
Convergence of Rump's method for computing the Moore-Penrose inverse (English) |
| Author:
|
Chen, Yunkun |
| Author:
|
Shi, Xinghua |
| Author:
|
Wei, Yimin |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
859-879 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
Moore-Penrose inverse |
| Keyword:
|
condition number |
| Keyword:
|
ill-conditioned matrix |
| MSC:
|
15A24 |
| MSC:
|
65F05 |
| idZBL:
|
Zbl 06644038 |
| idMR:
|
MR3556872 |
| DOI:
|
10.1007/s10587-016-0297-3 |
| . |
| Date available:
|
2016-10-01T15:31:03Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145876 |
| . |
| Reference:
|
[1] Ben-Israel, A., Greville, T. N. E.: Generalized Inverses. Theory and Applications.Springer, New York (2003). Zbl 1026.15004, MR 1987382 |
| Reference:
|
[2] Björck, Å.: Numerical Methods for Least Squares Problems.Society for Industrial and Applied Mathematics (SIAM) Philadelphia (1996). Zbl 0847.65023, MR 1386889 |
| Reference:
|
[3] Campbell, S. L., Meyer, C. D.: Generalized Inverses of Linear Transformations.Dover Publications, New York (1991). Zbl 0732.15003, MR 1105324 |
| Reference:
|
[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. Zbl 1296.65060, MR 3082494, 10.1137/12088642X |
| Reference:
|
[5] Chen, L., Krishnamurthy, E. V., Madeod, I.: Generalised matrix inversion and rank computation by successive matrix powering.Parallel Comput. 20 (1994), 297-311. MR 1267509, 10.1016/S0167-8191(06)80014-1 |
| Reference:
|
[6] Courrieu, P.: Fast computation of Moore-Penrose inverse matrices.Neural Information Processing 8 (2005), 25-29. |
| Reference:
|
[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. Zbl 1115.15004, MR 2291844, 10.1090/S0025-5718-06-01913-2 |
| Reference:
|
[8] Cucker, F., Diao, H., Wei, Y.: Smoothed analysis of some condition numbers.Numer. Linear Algebra Appl. 13 (2006), 71-84. Zbl 1198.65084, MR 2194973, 10.1002/nla.464 |
| Reference:
|
[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. Zbl 0952.65032, MR 1723709 |
| Reference:
|
[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. MR 2738180, 10.1145/1462173.1462177 |
| Reference:
|
[11] Demmel, J., Higham, N. J.: Improved error bounds for underdetermined system solvers.SIAM J. Matrix Anal. Appl. 14 (1993), 1-14. MR 1199540, 10.1137/0614001 |
| Reference:
|
[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. Zbl 1199.65128, MR 2353687, 10.1002/nla.540 |
| Reference:
|
[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. Zbl 1346.65015, MR 3523006, 10.1016/j.cam.2016.05.023 |
| Reference:
|
[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. Zbl 1251.65040, MR 2954742, 10.1093/imanum/drr023 |
| Reference:
|
[15] Fiedler, M.: Moore-Penrose biorthogonal systems in Euclidean spaces.Linear Algebra Appl. 362 (2003), 137-143. Zbl 1022.15004, MR 1955460, 10.1016/S0024-3795(02)00510-4 |
| Reference:
|
[16] Fiedler, M., Markham, T. L.: A characterization of the Moore-Penrose inverse.Linear Algebra Appl. 179 (1993), 129-133. Zbl 0764.15003, MR 1200147 |
| Reference:
|
[17] Golub, G. H., Loan, C. F. Van: Matrix Computations.Johns Hopkins Studies in the Mathematical Sciences Johns Hopkins University Press, Baltimore (2013). MR 3024913 |
| Reference:
|
[18] Gulliksson, M., Wedin, P. Å., Wei, Y.: Perturbation identities for regularized Tikhonov inverses and weighted pseudoinverses.BIT 40 (2000), 513-523. MR 1780405, 10.1023/A:1022319830134 |
| Reference:
|
[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. Zbl 0894.68088, MR 1600622, 10.1006/jsco.1997.0168 |
| Reference:
|
[20] Katsikis, V. N., Pappas, D.: Fast computing of the Moore-Penrose inverse matrix.Electron. J. Linear Algebra (electronic only) 17 (2008), 637-650. Zbl 1176.65048, MR 2460879 |
| Reference:
|
[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 3495915 |
| Reference:
|
[22] Li, Z., Xu, Q., Wei, Y.: A note on stable perturbations of Moore-Penrose inverses.Numer. Linear Algebra Appl. 20 (2013), 18-26. Zbl 1289.65091, MR 3007236, 10.1002/nla.838 |
| Reference:
|
[23] Ogita, T., Rump, S. M., Oishi, S.: Accurate sum and dot product.SIAM J. Sci. Comput. 26 (2005), 1955-1988. Zbl 1084.65041, MR 2196584, 10.1137/030601818 |
| Reference:
|
[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. |
| Reference:
|
[25] Oishi, S., Rump, S. M.: Fast verification of solutions of matrix equations.Numer. Math. 90 (2002), 755-773. Zbl 0999.65015, MR 1888837, 10.1007/s002110100310 |
| Reference:
|
[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. Zbl 1120.65040, MR 2324858, 10.1016/j.cam.2006.05.022 |
| Reference:
|
[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 0338013 |
| Reference:
|
[28] Rump, S. M.: Verified bounds for least squares problems and underdetermined linear systems.SIAM J. Matrix Anal. Appl. 33 (2012), 130-148. Zbl 1255.65082, MR 2902675, 10.1137/110840248 |
| Reference:
|
[29] Rump, S. M.: Inversion of extremely ill-conditioned matrices in floating-point.Japan J. Ind. Appl. Math. 26 (2009), 249-277. Zbl 1185.65050, MR 2589475, 10.1007/BF03186534 |
| Reference:
|
[30] Rump, S. M.: INTLAB---Interval Laboratory, the Matlab toolbox for verified computations, Version 5.3.Institute for Reliable Computing, Hamburg (2006). |
| Reference:
|
[31] Rump, S. M.: Ill-conditioned matrices are componentwise near to singularity.SIAM Rev. 41 (1999), 102-112. Zbl 0923.15003, MR 1669725, 10.1137/S0036144598323216 |
| Reference:
|
[32] Rump, S. M.: Ill-conditionedness need not be componentwise near to ill-posedness for least squares problems.BIT 39 (1999), 143-151. Zbl 0970.65039, MR 1682400, 10.1023/A:1022377410087 |
| Reference:
|
[33] Rump, S. M.: A class of arbitrarily ill-conditioned floating-point matrices.SIAM J. Matrix Anal. Appl. 12 (1991), 645-653. Zbl 0738.65042, MR 1121698, 10.1137/0612049 |
| Reference:
|
[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). |
| Reference:
|
[35] Smoktunowicz, A., Barlow, J., Langou, J.: A note on the error analysis of classical Gram-Schmidt.Numer. Math. 105 (2006), 299-313. Zbl 1108.65021, MR 2262760, 10.1007/s00211-006-0042-1 |
| Reference:
|
[36] Smoktunowicz, A., Wróbel, I.: Numerical aspects of computing the Moore-Penrose inverse of full column rank matrices.BIT 52 (2012), 503-524. Zbl 1251.65053, MR 2931361, 10.1007/s10543-011-0362-0 |
| Reference:
|
[37] Stewart, G. W.: On the perturbation of pseudo-inverses, projections and linear least squares problems.SIAM Rev. 19 (1977), 634-662. MR 0461871, 10.1137/1019104 |
| Reference:
|
[38] Wang, G., Wei, Y., Qiao, S.: Generalized Inverses: Theory and Computations.Science Press, Beijing (2004). MR 3793648 |
| Reference:
|
[39] Wedin, P. Å.: Perturbation theory for pseudo-inverses.BIT, Nord. Tidskr. Inf.-behandl. 13 (1973), 217-232. Zbl 0263.65047, MR 0336982 |
| Reference:
|
[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 3013937 |
| Reference:
|
[41] Wei, Y., Ding, J.: Representations for Moore-Penrose inverses in Hilbert spaces.Appl. Math. Lett. 14 (2001), 599-604. Zbl 0982.47003, MR 1832670, 10.1016/S0893-9659(00)00200-7 |
| Reference:
|
[42] Wei, Y., Wu, H.: Expression for the perturbation of the weighted Moore-Penrose inverse.Comput. Math. Appl. 39 (2000), 13-18. Zbl 0957.15003, MR 1742470, 10.1016/S0898-1221(00)00041-9 |
| Reference:
|
[43] Wei, Y., Xie, P., Zhang, L.: Tikhonov regularization and randomized GSVD.SIAM J. Matrix Anal. Appl. 37 (2016), 649-675. Zbl 1339.65057, MR 3502609, 10.1137/15M1030200 |
| Reference:
|
[44] Xu, W., Wei, Y., Qiao, S.: Condition numbers for structured least squares problems.BIT 46 (2006), 203-225. Zbl 1093.65045, MR 2214856, 10.1007/s10543-006-0049-0 |
| Reference:
|
[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. Zbl 1171.65031, MR 2505849, 10.1007/s11075-009-9269-0 |
| Reference:
|
[46] Zielke, G.: Report on test matrices for generalized inverses.Computing 36 (1986), 105-162. Zbl 0566.65026, MR 0832934, 10.1007/BF02238196 |
| . |
