Singular Value Computations for Toeplitz Matrices and Subspace Tracking

Sammanfattning: This thesis addresses the problem of computing the largest singular values and corresponding singular vectors of a Toeplitz matrix. These are often requested in signal processing and system identification to extract the signal from the noise.Toeplitz matrices resemble sparse matrices in the sense that the matrix-vector multiplication can be computed efficiently. For Toeplitz matrices this can be done by using the FFT. These similarities make it reasonable to study methods developed for sparse matrices. We compare different algorithms, mainly based on the Lanczos procedure, for computing a few singular values. We give a theoretical review of the methods and perform numerical tests to compare their performance.A Toeplitz matrix can easily be transformed into a Hankel matrix, which is symmetric. We derive a new algorithm for computing a few singular triplets of a complex symmetric matrix. The algorithm resembles the Lanczos procedure for Hermitian matrices, but computes the partial singular value decomposition directly. Theoretical results are deduced concerning singular value bounds and relations to the block Lanczos method and numerical experiments show the method to be powerful.We also address the subspace tracking problem. This problem involves computing several partial singular value decompositions successively, and arises, for instance, when a system varies with time. A new Lanczos like algorithm is derived, which computes the partial eigendecomposition of matrices which differ by a rank-one matrix. The method explicitly utilizes the structure in the update and uses a modified version of the Implicitly Restarted Lanczos (IRL) to speed up the convergence. The method is compared to IRL numerically and shows good behavior, especially when the matrices have multiple or clustered eigenvalues.The subspace tracking problem for more general updates can be solved by using the Newton method on the Grassman manifold. We give a theoretical review of this method and discuss implementation aspects such as how to solve the Sylvester equation involved.