Solving Toeplitz least-squares problems via discrete polynomial least-squares approximation at roots of unity
Marc Van Barel, Georg Heinig, Peter Kravanja · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2000
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 approach is numerically stable even for ill-conditioned problems.