Academy of Mathematics and Systems Science, CAS Colloquia & Seminars
Speaker:
Yimin Wei, Fudan University
Inviter:
Title:
Statistical Condition Estimates and Randomized Algorithms for Large-Scale Total Least Squares Problems
Time & Venue:
2018.11.1 10:00 N205
Abstract:
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 (TLS) problem with a single right-hand side. We present the Nystr¨om method (NTLS) for the medium-sized problems. For the large-scale and ill-conditioned cases we introduce the randomized truncated Tls (Rttls) with the known or estimated rank as regularization parameter. We analyze the accuracy of the algorithm Rttls, 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. Under the genericity condition, we study the condition estimation of the total least squares (TLS) problem based on small sample condition estimation (SCE), which can be incorporated into the direct solver for the TLS problem via the singular value decomposition (SVD) of the augmented matrix [A, b]. Our proposed condition estimation algorithms are efficient for the small and medium size TLS problem because they utilize the computed SVD of [A, b] during the numerical solution to the TLS problem. Numerical examples illustrate the reliability of the algorithms. Both normwise and componentwise perturbations are considered. Moreover, structured condition estimations are investigated for the structured TLS problem.