Superfast Tikhonov Regularization of Toeplitz Systems

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 O(n²) 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 O(KNlog² N) operations, where K is the number of regularizers and N 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.