Premium
Randomized algorithms for total least squares problems
Author(s) -
Xie Pengpeng,
Xiang Hua,
Wei Yimin
Publication year - 2019
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2219
Subject(s) - randomized algorithm , mathematics , algorithm , regularization (linguistics) , least squares function approximation , probabilistic analysis of algorithms , rank (graph theory) , probabilistic logic , total least squares , generalized least squares , non linear least squares , statistics , computer science , estimation theory , artificial intelligence , combinatorics , estimator , singular value decomposition
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.