Previous |  Up |  Next

Article

Keywords:
Moore-Penrose inverse; condition number; ill-conditioned matrix
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.
References:
[1] Ben-Israel, A., Greville, T. N. E.: Generalized Inverses. Theory and Applications. Springer, New York (2003). MR 1987382 | Zbl 1026.15004
[2] Björck, Å.: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics (SIAM) Philadelphia (1996). MR 1386889 | Zbl 0847.65023
[3] Campbell, S. L., Meyer, C. D.: Generalized Inverses of Linear Transformations. Dover Publications, New York (1991). MR 1105324 | Zbl 0732.15003
[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 10.1137/12088642X | MR 3082494 | Zbl 1296.65060
[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 10.1016/S0167-8191(06)80014-1 | MR 1267509
[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 10.1090/S0025-5718-06-01913-2 | MR 2291844 | Zbl 1115.15004
[8] Cucker, F., Diao, H., Wei, Y.: Smoothed analysis of some condition numbers. Numer. Linear Algebra Appl. 13 (2006), 71-84. DOI 10.1002/nla.464 | MR 2194973 | Zbl 1198.65084
[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 1723709 | Zbl 0952.65032
[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 10.1145/1462173.1462177 | MR 2738180
[11] Demmel, J., Higham, N. J.: Improved error bounds for underdetermined system solvers. SIAM J. Matrix Anal. Appl. 14 (1993), 1-14. DOI 10.1137/0614001 | MR 1199540
[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 10.1002/nla.540 | MR 2353687 | Zbl 1199.65128
[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 10.1016/j.cam.2016.05.023 | MR 3523006 | Zbl 1346.65015
[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 10.1093/imanum/drr023 | MR 2954742 | Zbl 1251.65040
[15] Fiedler, M.: Moore-Penrose biorthogonal systems in Euclidean spaces. Linear Algebra Appl. 362 (2003), 137-143. DOI 10.1016/S0024-3795(02)00510-4 | MR 1955460 | Zbl 1022.15004
[16] Fiedler, M., Markham, T. L.: A characterization of the Moore-Penrose inverse. Linear Algebra Appl. 179 (1993), 129-133. MR 1200147 | Zbl 0764.15003
[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
[18] Gulliksson, M., Wedin, P. Å., Wei, Y.: Perturbation identities for regularized Tikhonov inverses and weighted pseudoinverses. BIT 40 (2000), 513-523. DOI 10.1023/A:1022319830134 | MR 1780405
[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 10.1006/jsco.1997.0168 | MR 1600622 | Zbl 0894.68088
[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 2460879 | Zbl 1176.65048
[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
[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 10.1002/nla.838 | MR 3007236 | Zbl 1289.65091
[23] Ogita, T., Rump, S. M., Oishi, S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26 (2005), 1955-1988. DOI 10.1137/030601818 | MR 2196584 | Zbl 1084.65041
[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 10.1007/s002110100310 | MR 1888837 | Zbl 0999.65015
[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 10.1016/j.cam.2006.05.022 | MR 2324858 | Zbl 1120.65040
[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
[28] Rump, S. M.: Verified bounds for least squares problems and underdetermined linear systems. SIAM J. Matrix Anal. Appl. 33 (2012), 130-148. DOI 10.1137/110840248 | MR 2902675 | Zbl 1255.65082
[29] Rump, S. M.: Inversion of extremely ill-conditioned matrices in floating-point. Japan J. Ind. Appl. Math. 26 (2009), 249-277. DOI 10.1007/BF03186534 | MR 2589475 | Zbl 1185.65050
[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 10.1137/S0036144598323216 | MR 1669725 | Zbl 0923.15003
[32] Rump, S. M.: Ill-conditionedness need not be componentwise near to ill-posedness for least squares problems. BIT 39 (1999), 143-151. DOI 10.1023/A:1022377410087 | MR 1682400 | Zbl 0970.65039
[33] Rump, S. M.: A class of arbitrarily ill-conditioned floating-point matrices. SIAM J. Matrix Anal. Appl. 12 (1991), 645-653. DOI 10.1137/0612049 | MR 1121698 | Zbl 0738.65042
[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 10.1007/s00211-006-0042-1 | MR 2262760 | Zbl 1108.65021
[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 10.1007/s10543-011-0362-0 | MR 2931361 | Zbl 1251.65053
[37] Stewart, G. W.: On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM Rev. 19 (1977), 634-662. DOI 10.1137/1019104 | MR 0461871
[38] Wang, G., Wei, Y., Qiao, S.: Generalized Inverses: Theory and Computations. Science Press, Beijing (2004). MR 3793648
[39] Wedin, P. Å.: Perturbation theory for pseudo-inverses. BIT, Nord. Tidskr. Inf.-behandl. 13 (1973), 217-232. MR 0336982 | Zbl 0263.65047
[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
[41] Wei, Y., Ding, J.: Representations for Moore-Penrose inverses in Hilbert spaces. Appl. Math. Lett. 14 (2001), 599-604. DOI 10.1016/S0893-9659(00)00200-7 | MR 1832670 | Zbl 0982.47003
[42] Wei, Y., Wu, H.: Expression for the perturbation of the weighted Moore-Penrose inverse. Comput. Math. Appl. 39 (2000), 13-18. DOI 10.1016/S0898-1221(00)00041-9 | MR 1742470 | Zbl 0957.15003
[43] Wei, Y., Xie, P., Zhang, L.: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37 (2016), 649-675. DOI 10.1137/15M1030200 | MR 3502609 | Zbl 1339.65057
[44] Xu, W., Wei, Y., Qiao, S.: Condition numbers for structured least squares problems. BIT 46 (2006), 203-225. DOI 10.1007/s10543-006-0049-0 | MR 2214856 | Zbl 1093.65045
[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 10.1007/s11075-009-9269-0 | MR 2505849 | Zbl 1171.65031
[46] Zielke, G.: Report on test matrices for generalized inverses. Computing 36 (1986), 105-162. DOI 10.1007/BF02238196 | MR 0832934 | Zbl 0566.65026
Partner of
EuDML logo