Title
A superfast method for solving Toeplitz linear least squares problems
Author
Faculty/Department
Faculty of Social Sciences. Communication Sciences
Publication type
article
Publication
New York, N.Y. ,
Subject
Mathematics
Source (journal)
Linear algebra and its applications. - New York, N.Y.
Volume/pages
366(2003) , p. 441-457
ISSN
0024-3795
ISI
000182667200025
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Abstract
In this paper we develop a superfast O((m + n) log2(m + n)) complexity algorithm to solve a linear least squares problem with an m × n Toeplitz coefficient matrix. The algorithm is based on the augmented matrix approach. The augmented matrix is further extended to a block circulant matrix and DFT is applied. This leads to an equivalent tangential interpolation problem where the nodes are roots of unity. This interpolation problem can be solved by a divide and conquer strategy in a superfast way. To avoid breakdowns and to stabilize the algorithm pivoting is used and a technique is applied that selects difficult points and treats them separately. The effectiveness of the approach is demonstrated by several numerical examples.
E-info
https://repository.uantwerpen.be/docman/iruaauth/8d6af7/10fcc75354d.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000182667200025&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000182667200025&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000182667200025&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848