Matrices with low-rank-plus-shift structure: Partial SVD and latent semantic indexing

We present a detailed analysis of matrices satisfying the so-called low-ran k-plus-shift property in connection with the computation of their partial s ingular value decomposition (SVD). The application we have in mind is laten t semantic indexing for information retrieval, where the term-document matr ices generated from a text corpus approximately satisfy this property. The analysis is motivated by developing more efficient methods for computing an d updating partial SVD of large term-document matrices and gaining deeper u nderstanding of the behavior of the methods in the presence of noise.