×

zbMATH — the first resource for mathematics

Randomized core reduction for discrete ill-posed problem. (English) Zbl 07183960
Summary: In this paper, we apply randomized algorithms to approximate the total least squares (TLS) solution of the problem \(A x \approx b\) in the large-scale discrete ill-posed problems. A regularization technique, based on the multiplicative randomization and the subspace iteration, is proposed to obtain the approximate core problem. In the error analysis, we provide upper bounds for the errors of the solution and the residual of the randomized core reduction. Illustrative numerical examples and comparisons are presented.
MSC:
15A09 Theory of matrix inversion and generalized inverses
65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Paige, C. C.; Strakos, Z., Core problems in linear algebraic systems, SIAM J. Matrix Anal. Appl., 27, 3, 861-875 (2005) · Zbl 1097.15003
[2] Hnětynková, I.; Plešinger, M.; Strakoš, Z., The core problem within a linear approximation problem \(A X \approx B\) with multiple right-hand sides, SIAM J. Matrix Anal. Appl., 34, 3, 917-931 (2013) · Zbl 1279.65041
[3] Hnětynková, I.; Plešinger, M.; Žáková, J., TLS formulation and core reduction for problems with structured right-hand sides, Linear Algebra Appl., 555, 241-265 (2018) · Zbl 1416.65103
[4] Van Huffel, S.; Vandewalle, J., The Total Least Squares Problem: Computational Aspects and Analysis (1991), SIAM: SIAM Philadelphia, PA · Zbl 0789.62054
[5] Lampe, J.; Voss, H., Solving regularized total least squares problems based on eigenproblems, Taiwanese J. Math., 14, 3A, 885-909 (2010) · Zbl 1198.65081
[6] Björck, Å.; Heggernes, P.; Matstoms, P., Methods for large scale total least squares problems, SIAM J. Matrix Anal. Appl., 22, 2, 413-429 (2000) · Zbl 0974.65037
[7] Fierro, R. D.; Golub, G. H.; Hansen, P. C.; O’Leary, D. P., Regularization by truncated total least squares, SIAM J. Sci. Comput., 18, 4, 1223-1241 (1997) · Zbl 0891.65040
[8] Fierro, R. D.; Bunch, J. R., Collinearity and total least squares, SIAM J. Matrix Anal. Appl., 15, 4, 1167-1181 (1994) · Zbl 0805.65042
[9] Hnětynková, I.; Plešinger, M.; Sima, D. M., Solvability of the core problem with multiple right-hand sides in the TLS sense, SIAM J. Matrix Anal. Appl., 37, 3, 861-876 (2016) · Zbl 1343.15002
[10] Hnětynková, I.; Plešinger, M.; Sima, D. M.; Strakoš, Z.; Van Huffel, S., The total least squares problem in \(A X \approx B\): a new classification with the relationship to the classical works, SIAM J. Matrix Anal. Appl., 32, 3, 748-770 (2011) · Zbl 1235.15016
[11] Hnětynková, I.; Plešinger, M.; Strakoš, Z., Band generalization of the Golub-Kahan bidiagonalization, generalized Jacobi matrices, and the core problem, SIAM J. Matrix Anal. Appl., 36, 2, 417-434 (2015) · Zbl 1320.65057
[12] Hnětynková, I.; Plešinger, M.; Žáková, J., TLS formulation and core reduction for problems with structured right-hand sides, Linear Algebra Appl., 555, 15, 241-265 (2018) · Zbl 1416.65103
[13] Zheng, B.; Meng, L.; Wei, Y., Condition numbers of the multidimensional total least squares problem, SIAM J. Matrix Anal. Appl., 38, 924-948 (2017) · Zbl 1373.65035
[14] Wang, X.-F., Total least squares problem with the arbitrary unitarily invariant norms, Linear Multilinear Algebra, 65, 3, 438-456 (2017) · Zbl 1367.15017
[15] Meng, X.; Saunders, M. A.; Mahoney, M. W., LSRN: a parallel iterative solver for strongly over- or underdetermined systems, SIAM J. Sci. Comput., 36, 2, C95-C118 (2014)
[16] Rokhlin, V.; Tygert, M., A fast randomized algorithm for overdetermined linear leastsquares regression, Proc. Natl. Acad. Sci. USA, 105, 36, 13212-13217 (2008) · Zbl 05851018
[17] Woolfe, F.; Liberty, E.; Rokhlin, V.; Tygert, M., A fast randomized algorithm for the approximation of matrices, Appl. Comput. Harmon. Anal., 25, 3, 335-366 (2008) · Zbl 1155.65035
[18] Avron, H.; Maymounkov, P.; Toledo, S., Blendenpik: Supercharging LAPACK’s leastsquares solver, SIAM J. Sci. Comput., 32, 3, 1217-1236 (2010) · Zbl 1213.65069
[19] Martinsson, P.-G.; Rokhlin, V.; Tygert, M., A randomized algorithm for the decomposition of matrices, Appl. Comput. Harmon. Anal., 30, 1, 47-68 (2011) · Zbl 1210.65095
[20] Coakley, E.; Rokhlin, V.; Tygert, M., A fast randomized algorithm for orthogonal projection, SIAM J. Sci. Comput., 33, 2, 849-868 (2011) · Zbl 1368.65061
[21] Rachkovskij, D.; Revunova, E., A randomized method for solving discrete ill-posed problems, Cybern. Syst. Anal., 48, 4, 621-635 (2012) · Zbl 1311.65043
[22] Halko, N.; Martinsson, P.-G.; Tropp, J. A., Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 2, 217-288 (2011) · Zbl 1269.65043
[23] Gu, M., Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37, 3, A1139-A1173 (2015) · Zbl 1328.65088
[24] Xiang, H.; Zou, J., Regularization with randomized SVD for large-scale discrete inverse problems, Inverse Problems, 29, 8, Article 085008 pp. (2013) · Zbl 1286.65053
[25] Xiang, H.; Zou, J., Randomized algorithms for large-scale inverse problems with general tikhonov regularizations, Inverse Problems, 31, 8, Article 085008 pp. (2015), 24 · Zbl 1327.65077
[26] Wei, Y.; Xie, P.; Zhang, L., Tikhonov regularization and randomized GSVD, SIAM J. Matrix Anal. Appl., 37, 649-675 (2016) · Zbl 1339.65057
[27] Jia, Z.; Yang, Y., Modified truncated randomized singular value decomposition (mtrsvd) algorithms for large scale discrete ill-posed problems with general-form regularization, Inverse Problems, 34, 5, Article 055013 pp. (2018) · Zbl 06897211
[28] Saibaba, A. K.; Lee, J.; Kitanidis, P. K., Randomized algorithms for generalized hermitian eigenvalue problems with application to computing Karhunen-Loeve expansion, Numer. Linear Algebra Appl., 23, 314-339 (2016) · Zbl 1413.65104
[29] Xie, P.; Wei, Y.; Xiang, H., Perturbation analysis and randomized algorithms for largescale total least squares problems, Numer. Linear Algebra Appl., 26, Article e2219 pp. (2019)
[30] Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037
[31] Deif, A., Sensitivity Analysis in Linear Systems (1986), Springer-Verlag: Springer-Verlag Berlin · Zbl 0624.65019
[32] Baboulin, M.; Gratton, S., A contribution to the conditioning of the total least-squares problem, SIAM J. Matrix Anal. Appl., 32, 3, 685-699 (2011) · Zbl 1242.65087
[33] Thompson, R. C., Principal submatrices IX: Interlacing inequalities for singular values of submatrices, Linear Algebra Appl., 5, 1-12 (1972) · Zbl 0252.15009
[34] Wedin, P.Å, Perturbation theory for pseudo-inverses, BIT, 13, 217-232 (1973) · Zbl 0263.65047
[35] Larsen, R. M., Lanczos bidiagonalization with partial reorthogonalization, DAIMI Rep. Ser., 27, 537 (1998)
[36] Larsen, R. M., Propack-software for large and sparse SVD calculations, 2008-2009 (2004), Available online at URL http://sun.stanford.edu/rmunk/PROPACK/
[37] Hansen, P. C., Regularization tools version 4.0 for matlab 7.3, Numer. Algorithms, 46, 2, 189-194 (2007) · Zbl 1128.65029
[38] Hansen, P. C.; Nagy, J. G.; O’Leary, D. P., Deblurring Images: Matrices, Spectra, and Filtering (2006), SIAM: SIAM Philadelphia, PA · Zbl 1112.68127
[39] Pruessner, A.; O’Leary, D. P., Blind deconvolution using a regularized structured total least norm algorithm, SIAM J. Matrix Anal. Appl., 24, 4, 1018-1037 (2003) · Zbl 1036.65036
[40] Gazzola, S.; Hansen, P. C.; Nagy, J. G., IR tools: a MATLAB package of iterative regularization methods and large-scale test problems, Numer. Algorithms, 81, 773-811 (2019) · Zbl 1415.65003
[41] Bai, Z.-Z.; Buccini, A.; Hayami, K.; Reichel, L.; Yin, J.-F.; Zheng, N., Modulus-based iterative methods for constrained Tikhonov regularization, J. Comput. Appl. Math., 319, 1-13 (2017) · Zbl 1360.65112
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.