Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Fast Algorithms for Structured Least Squares



Anoop Kalsi, Dianne M. O'Leary


We consider the problem of solving least squares problems involving a matrix M of small displacement rank with respect to two matrices Z1 and Z2. We develop formulas for the generators of the matrix MHM in terms of the generators of M and show that the Cholesky factorization of the matrix MHM can be computed quickly if Z1 is close to unitary and Z2 is triangular and nilpotent. These conditions are satisfied for several classes of matrices, including Toeplitz, block Toeplitz, Hankel, and block Hankel, and for matrices whose blocks have such structure. Fast Cholesky factorization enables fast solution of least squares problems, total least squares problems, and regularized total least squares problems involving these classes of matrices.
Journal of Research (NIST JRES) -


block Toeplitz matrix, Displacement rank, errors in variables method, structured total least squares, total least squares


Kalsi, A. and O'Leary, D. (2006), Fast Algorithms for Structured Least Squares, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed June 20, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created March 31, 2006, Updated October 12, 2021