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

Published

Author(s)

Anoop Kalsi, Dianne M. O'Leary

Abstract

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.
Citation
Journal of Research (NIST JRES) -
Volume
111
Issue
2

Keywords

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

Citation

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], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50670 (Accessed June 20, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created March 31, 2006, Updated October 12, 2021