1 December 1991 Some fast Toeplitz least-squares algorithms
Author Affiliations +
Abstract
We study fast preconditioned conjugate gradient (PCG) methods for solving least squares problems min (parallel)b-T(chi) (parallel)2, where T is an m X n Toeplitz matrix of rank n. Two circulant preconditioners are suggested: one, denoted by P, is based on a block partitioning of T and the other, denoted by N, is based on the displacement representation of TTT. Each is obtained without forming TTT. We prove formally that for a wide class of problems the PCG method with P converges in a small number of iterations independent of m and n, so that the computational cost of solving such Toeplitz least squares problems is O(m log n). Numerical experiments in using both P and N are reported, indicating similar good convergence properties for each preconditioner.
© (1991) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
James G. Nagy, Robert J. Plemmons, "Some fast Toeplitz least-squares algorithms", Proc. SPIE 1566, Advanced Signal Processing Algorithms, Architectures, and Implementations II, (1 December 1991); doi: 10.1117/12.49810; https://doi.org/10.1117/12.49810
PROCEEDINGS
12 PAGES


SHARE
RELATED CONTENT

Approximation by structured lower rank matrices
Proceedings of SPIE (October 02 1998)
Two-step Gram-Schmidt downdating methods
Proceedings of SPIE (November 20 2001)
Block circulant preconditioners for 2D deconvolution
Proceedings of SPIE (November 30 1992)
Alternative To The SVD: Rank Revealing QR-Factorizations
Proceedings of SPIE (April 04 1986)
Minimal-window time-frequency distributions
Proceedings of SPIE (November 02 1999)

Back to Top