Randomized algorithms for total least squares problems. (English) Zbl 1524.65181
Summary: Motivated by the recently popular probabilistic methods for low-rank approximations and randomized algorithms for the least squares problems, we develop randomized algorithms for the total least squares problem with a single right-hand side. We present the Nyström method for the medium-sized problems. For the large-scale and ill-conditioned cases, we introduce the randomized truncated total least squares with the known or estimated rank as the regularization parameter. We analyze the accuracy of the algorithm randomized truncated total least squares and perform numerical experiments to demonstrate the efficiency of our randomized algorithms. The randomized algorithms can greatly reduce the computational time and still maintain good accuracy with very high probability.
MSC:
| 65F25 | Orthogonalization in numerical linear algebra |
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 65K10 | Numerical optimization and variational techniques |
Keywords:
Golub-Kahan bidiagonalization; Lanczos tridiagonalization; Nyström method; randomized algorithms; singular value decomposition; total least squares; truncated total least squaresReferences:
| [1] | Van HuffelS, VandewalleJ. The total least squares problem: computational aspects and analysis. Philadelphia, PA: SIAM; 1991. · Zbl 0789.62054 |
| [2] | GolubGH, Van LoanCF. An analysis of the total least squares problem. SIAM J Numer Anal. 1980;17(6):883-893. · Zbl 0468.65011 |
| [3] | WeiM. Algebraic relations between the total least squares and least squares problems with more than one solution. Numer Math. 1992;62(1):123-148. · Zbl 0761.65030 |
| [4] | MastronardiN, LemmerlingP, KalsiA, O’LearyDP, Van HuffelS. Implementation of the regularized structured total least squares algorithms for blind image deblurring. Linear Algebra Appl. 2004;391:203-221. · Zbl 1060.94502 |
| [5] | Van HuffelS, editor. Recent advances in total least squares techniques and errors‐in‐variables modeling. Philadelphia, PA: SIAM; 1997. · Zbl 0861.00018 |
| [6] | HansenPC, NagyJG, O’learyDP. Deblurring images: matrices, spectra and filtering. Vol. 3. Philadelphia, PA: SIAM; 2006. · Zbl 1112.68127 |
| [7] | LeeG, FuH, BarlowJL. Fast high‐resolution image reconstruction using Tikhonov regularization based total least squares. SIAM J Sci Comput. 2013;35(1):B275-B290. · Zbl 1267.65027 |
| [8] | HnětynkováI, PlešingerM, SimaDM, StrakošZ, Van HuffelS. The total least squares problem in AX≈B: a new classification with the relationship to the classical works. SIAM J Matrix Anal Appl. 2011;32(3):748-770. · Zbl 1235.15016 |
| [9] | HnětynkováI, PlešingerM, StrakošZ. The core problem within a linear approximation problem AX≈B with multiple right‐hand sides. SIAM J Matrix Anal Appl. 2013;34:917-931. · Zbl 1279.65041 |
| [10] | HnětynkováI, PlešsingerM, StrakošZ. Band generalization of the Golub‐Kahan bidiagonalization, generalized Jacobi matrices, and the core problem. SIAM J Matrix Anal Appl. 2015;36:417-434. · Zbl 1320.65057 |
| [11] | HnětynkováI, PlešingerM, SimaDM. Solvability of the core problem with multiple right‐hand sides in TLS sense. SIAM J Matrix Anal Appl. 2016;37:861-876. · Zbl 1343.15002 |
| [12] | Van HuffelS. Partial singular value decomposition algorithm. J Comput Appl Math. 1990;33(1):105-112. · Zbl 0721.65016 |
| [13] | FierroRD, GolubGH, HansenPC, O’learyDP. Regularization by truncated total least squares. SIAM J Sci Comput. 1997;18(4):1223-1241. · Zbl 0891.65040 |
| [14] | O’LearyDP, SimmonsJA. A bidiagonalization‐regularization procedure for large scale discretizations of ill‐posed problems. SIAM J Sci Comput. 1981;2(4):474-489. · Zbl 0469.65089 |
| [15] | BjörckÅ. A bidiagonalization algorithm for solving large and sparse ill‐posed systems of linear equations. BIT Numer Math. 1988;28(3):659-670. · Zbl 0658.65041 |
| [16] | GolubGH, KahanW. Calculating the singular values and pseudo‐inverse of a matrix. J Soc Indust Appl Math Ser B Numer Anal. 1965;2:205-224. · Zbl 0194.18201 |
| [17] | LiesenJ, StrakošZ. Krylov subspace methods Principles and analysis. Oxford, UK: Oxford University Press; 2013. Numerical mathematics and scientific computation. · Zbl 1263.65034 |
| [18] | HalkoN, MartinssonPG, TroppJA. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 2011;53(2):217-288. · Zbl 1269.65043 |
| [19] | DrineasP, MahoneyMW, MuthukrishnanS, SarlósT. Faster least squares approximation. Numer Math. 2011;117(2):219-249. · Zbl 1218.65037 |
| [20] | RokhlinV, TygertM. A fast randomized algorithm for overdetermined linear least‐squares regression. Proc Natl Acad Sci. 2008;105(36):13212-13217. · Zbl 1513.62144 |
| [21] | AvronH, MaymounkovP, ToledoS. Blendenpik: supercharging LAPACK’s least‐squares solver. SIAM J Sci Comput. 2010;32(3):1217-1236. · Zbl 1213.65069 |
| [22] | CoakleyES, RokhlinV, TygertM. A fast randomized algorithm for orthogonal projection. SIAM J Sci Comput. 2011;33(2):849-868. · Zbl 1368.65061 |
| [23] | MengX, SaundersMA, MahoneyMW. LSRN: a parallel iterative solver for strongly over‐ or underdetermined systems. SIAM J Sci Comput. 2014;36(2):C95-C118. · Zbl 1298.65053 |
| [24] | XiangH, ZouJ. Regularization with randomized SVD for large‐scale discrete inverse problems. Inverse Probl. 2013;29(8):085008. · Zbl 1286.65053 |
| [25] | XiangH, ZouJ. Randomized algorithms for large‐scale inverse problems with general Tikhonov regularizations. Inverse Probl. 2015;31:085008. · Zbl 1327.65077 |
| [26] | WeiY, XieP, ZhangL. Tikhonov regularization and randomized GSVD. SIAM J Matrix Anal Appl. 2016;37(2):649-675. · Zbl 1339.65057 |
| [27] | GolubGH, Van LoanCF. Matrix computations. 4th ed.Baltimore, MD:Johns Hopkins University Press; 2013. Johns Hopkins studies in the mathematical sciences. · Zbl 1268.65037 |
| [28] | PaigeCC, StrakošZ. Core problems in linear algebraic systems. SIAM J Matrix Anal Appl. 2005;27(3):861-875. · Zbl 1097.15003 |
| [29] | WeiM. The analysis for the total least squares problem with more than one solution. SIAM J Matrix Anal Appl. 1992;13(3):746-763. · Zbl 0758.65039 |
| [30] | DrineasP, MahoneyMW. On the Nyström method for approximating a Gram matrix for improved kernel‐based learning. J Mach Learn Res. 2005;6:2153-2175. · Zbl 1222.68186 |
| [31] | DemmelJW. Applied numerical linear algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics; 1997. · Zbl 0879.65017 |
| [32] | BeckA, Ben‐TalA. On the solution of the Tikhonov regularization of the total least squares problem. SIAM J Optim. 2006;17(1):98-118. · Zbl 1112.65034 |
| [33] | GolubGH, HansenPC, O’learyDP. Tikhonov regularization and total least squares. SIAM J Matrix Anal Appl. 1999;21(1):185-194. · Zbl 0945.65042 |
| [34] | LampeJ, VossH. Large‐scale Tikhonov regularization of total least squares. J Comput Appl Math. 2013;238:95-108. · Zbl 1254.65052 |
| [35] | LuS, PereverzevSV, TautenhahnU. Regularized total least squares: computational aspects and error bounds. SIAM J Matrix Anal Appl. 2009;31(3):918-941. · Zbl 1198.65094 |
| [36] | BeckA, Ben‐TalA, TeboulleM. Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares. SIAM J Matrix Anal Appl. 2006;28(2):425-445. · Zbl 1115.65065 |
| [37] | LampeJ, VossH. Global convergence of RTLSQEP: a solver of regularized total least squares problems via quadratic eigenproblems. Math Model Anal. 2008;13(1):55-66. · Zbl 1151.65033 |
| [38] | RenautRA, GuoH. Efficient algorithms for solution of regularized total least squares. SIAM J Matrix Anal Appl. 2004;26(2):457-476. · Zbl 1082.65045 |
| [39] | SimaDM, Van HuffelS, GolubGH. Regularized total least squares based on quadratic eigenvalue problem solvers. BIT. 2004;44(4):793-812. · Zbl 1079.65048 |
| [40] | HnětynkováI, PlešingerM, ŽákováJ. Filter factors of truncated TLS regularization with multiple observations. Appl Math. 2017;62(2):105-120. · Zbl 1458.15017 |
| [41] | GrattonS, Titley‐PeloquinD, IlungaJT. Sensitivity and conditioning of the truncated total least squares solution. SIAM J Matrix Anal Appl. 2013;34(3):1257-1276. · Zbl 1312.65060 |
| [42] | MarkovskyI, Van HuffelS. Overview of total least‐squares methods. Signal Process. 2007;87(10):2283-2302. · Zbl 1186.94229 |
| [43] | HansenPC. Regularization tools: a Matlab package for analysis and solution of discrete ill‐posed problems. Numer Algorithms. 1994;6(1-2):1-35. · Zbl 0789.65029 |
| [44] | BaboulinM, GrattonS. A contribution to the conditioning of the total least‐squares problem. SIAM J Matrix Anal Appl. 2011;32(3):685-699. · Zbl 1242.65087 |
| [45] | RahmanMD, YuK‐B. Total least squares approach for frequency estimation using linear prediction. IEEE Trans Acoust Speech Signal Process. 1987;35(10):1440-1454. |
| [46] | MajdaG, StraussWA, WeiM. Computation of exponentials in transient data. IEEE Trans Antennas Propag. 1989;37(10):1284-1290. · Zbl 0946.78520 |
| [47] | WeiM, MajdaG. A new theoretical approach for Prony’s method. Linear Algebra Appl. 1990;136:119-132. · Zbl 0711.62082 |
| [48] | LarsenRM. Lanczos bidiagonalization with partial reorthogonalization (DAIMI Report Series). Aarhus, Denmark: Department of Computer Science, Aarhus University. 1998. http://sun.stanford.edu/ rmunk/PROPACK/ |
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.
