Solving Toeplitz least squares problems via discrete polynomial least squares approximation at roots of unity

摘要

We present an algorithm for solving Toeplitz least squares problems. By embedding the Toeplitz matrix into a circulant block matrix and by applying the Discrete Fourier Transform, we are able to transform the linear least squares problem into a discrete least squares approximation problem for polynomial vectors. We have implemented our algorithm in Matlab. Numerical experiments indicate that our approac is numerically stable even for illconditioned problems.