Divide-and-Conquer Solutions of Least-Squares Problems for Matrices with Displacement Structure
Joohwan Chun, T. Kailath · SIAM Journal on Matrix Analysis and Applications · 1991
A divide-and-conquer implementation of a generalized Schur algorithm enables (exact and) least-squares solutions of various block-Toeplitz or Toeplitz-block systems of equations with $O ( \alpha ^3 n\log ^2 n )$ operations to be obtained, where the displacement rank $\alpha $ is a small constant (typically between two to four for scalar near-Toeplitz matrices) independent of the size of the matrices.