Loyce Adams, Department of Applied Mathematics, University of Washington
Computing Factorizations of Matrices Perturbed by Small-Rank Updates
Abstract: Computing factorizations of matrices is an important first step in the efficient solution of many scientific problems. A common application problem is that of producing a model that predicts known data, typically in the least squares sense For this problem, a relevant factorization is the singular value decomposition (SVD) which can be used even if the problem matrix is rank-deficient. The computation of the SVD takes O(mn^2) work for an m x n matrix. If we change the matrix (hence the model), do we have to pay this same cost to factor the new matrix? Of course this depends on how we change the matrix. One could consider adding rows or columns. Instead, this talk addresses the question: If we know the SVD of a matrix, can we use this efficiently to compute the SVD of its sum with another matrix of low-rank? We answer this question for various cases, starting with specific perturbations associated with known results, and moving to more complicated cases. This work shows that two different strategies prove useful in finding the singular values of the new matrix for the cases involving non-symmetric perturbations. One involves the solution of three symmetric perturbation problems for the singular values coupled with a formula for the singular vectors. The other finds roots of a secular equation coupled with the same formula for the singular vectors.
