Some fast Toeplitz least-squares algorithms

摘要

We study fast preconditioned conjugate gradient (PCG) methods for solving least squares problems min $PLL@b$MIN@T$chi$PLL$-2$/, where T is an m $MUL 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 T$+T$/T. Each is obtained without forming T$+T$/T. 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.