Translator Disclaimer
1 December 1991 Some fast Toeplitz least-squares algorithms
Author Affiliations +
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 and Robert J. Plemmons "Some fast Toeplitz least-squares algorithms", Proc. SPIE 1566, Advanced Signal Processing Algorithms, Architectures, and Implementations II, (1 December 1991);


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

Back to Top