Two uses for updating the partial singular value decomposition in latent semantic indexing

Latent Semantic Indexing (LSI) is an information retrieval (IR) method that con-nects IR with numerical linear algebra by representing a dataset as a term-document matrix. Because of the tremendous size of modern databases, such matrices can be very large. The partial singular value decomposition (PSVD) is a matrix factoriza-tion that captures the salient features of a matrix, while using much less storage. We look at two challenges posed by this PSVD data compression process in LSI. Traditional methods of computing the PSVD are very expensive; most of the pro-cessing time in LSI is spent in calculating the PSVD of the term-document matrix. Thus, the first challenge is calculating the PSVD efficiently, in terms of computa-tional and memory requirements. The second challenge is efficiently updating the PSVD when the matrix is altered slightly. In a rapidly expanding environment, such as the Internet, the term-document matrix is altered often as new documents and terms are added. Updating the PSVD of this matrix is much more efficient than recalculating it after each change. We investigate the use of the PSVD updating methods proposed by Zha and Simon (1999, SIAM J. Sci. Comput., 21, 2) to meet both of these challenges. Results are presented illustrating that updating in this Preprint submitted to Elsevier Science 15 July 2005 manner provides tremendous savings in computation time, with little or no signifi-cant reduction in accuracy. An algorithm for iteratively computing the PSVD of a matrix using the document updating method will then be presented. This iterative method, suggested by Zha and Zhang (1999, SIAM J. Matrix Anal. Appl., 21, 2), provides a means of calculating the PSVD for matrices so large that the computa-tion would be infeasible using traditional methods. Again, results are given showing that this method provides savings in computational time and memory resources without compromising the accuracy of the results. Key words: partial singular value decomposition, updating, latent semantic indexing, iterative methods 1991 MSC: 15A18