Fast computation of the principal singular vectors of Toeplitz matrices arising in exponential data modelling

A comparison is made of algorithms for computing the largest singular values and corresponding singular vectors of a Toeplitz matrix. In many applications the signal subspace is the subspace spanned by those singular vectors. Algorithms, based on the Lanczos procedure, for computing a few singular values of a sparse matrix are discussed, and the fast Fourier transform (FFT) is used for the matrix-vector multiplication. In particular, we consider a recently developed implicitly restarted Lanczos algorithm, and we give evidence that for Toeplitz matrices arising in exponential data modelling, this algorithm is both more efficient and more reliable than other Lanczos variants. Numerical tests also indicate that this algorithm may be up to one hundred times faster than standard algorithms (from LAPACK) even for problems of modest size.