Superfast Tikhonov Regularization of Toeplitz Systems

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. Early “fast” algorithms required <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$ {\cal O}(n^{2})$</tex></formula> operations, but recent “superfast” algorithms are more efficient. 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 <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$ {\cal O}(KN\log ^{2} N)$</tex></formula> operations, where <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$K$</tex></formula> is the number of regularizers and <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$N$</tex></formula> is on the order of the number of parameters defining the system matrix. Our algorithm is further improved with displacement structure, which reduces the complexity when solving the system for multiple input vectors. We use numerical simulations to demonstrate our algorithm's complexity and accuracy.

Locations

• IEEE Transactions on Signal Processing - View
• arXiv (Cornell University) - View - PDF
• DataCite API - View