On the Efficient Update of the Singular Value Decomposition Subject to Rank-One Modifications

In this paper we present an efficient method for updating the singular value decomposition (SVD) subject to a rank-one modification. The updated SVD can be characterized by two problems involving symmetric matrices. The singular values corresponding to these symmetric problems are computed by solving a secular equation. The secular equation can be solved reliably and efficiently with standard software. The singular vectors can be updated efficiently with a few matrix-matrix products. The computational effort to compute the matrix-matrix products can be considerably decreased by exploiting that some matrices are of Cauchy-type. We analyze several methods which exploit this structure. The computational complexity of the proposed approach is O(n2 log2 n).