Superfast Tikhonov Regularization of Toeplitz Systems
From MaRDI portal
Publication:4579338
DOI10.1109/TSP.2014.2330800zbMATH Open1392.65105arXiv1302.6945MaRDI QIDQ4579338FDOQ4579338
Authors: Christopher K. Turnes, Doru C. Balcan, Justin Romberg 
Publication date: 22 August 2018
Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)
Abstract: Toeplitz-structured linear systems arise often in practical engineering problems. Correspondingly, a number of algorithms have been developed that exploit Toeplitz structure to gain computational efficiency when solving these systems. The earliest "fast" algorithms for Toeplitz systems required O(n^2) operations, while more recent "superfast" algorithms reduce the cost to O(n (log n)^2) or below. In this work, we present a superfast algorithm for Tikhonov regularization of Toeplitz systems. Using an "extension-and-transformation" technique, our algorithm translates a Tikhonov-regularized Toeplitz system into a type of specialized polynomial problem known as tangential interpolation. Under this formulation, we can compute the solution in only O(n (log n)^2) operations. We use numerical simulations to demonstrate our algorithm's complexity and verify that it returns stable solutions.
Full work available at URL: https://arxiv.org/abs/1302.6945
Ill-posedness and regularization problems in numerical linear algebra (65F22) Toeplitz, Cauchy, and related matrices (15B05)
This page was built for publication: Superfast Tikhonov Regularization of Toeplitz Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579338)
