Limited-Memory Matrix Methods with Applications
Abstract
The focus of this dissertation is on matrix decompositions that use a
limited amount of computer memory, thereby allowing problems with a
very large number of variables to be solved. Specifically, we will
focus on two applications areas: optimization and information
retrieval.
We introduce a general algebraic form for the matrix update in
limited-memory quasi-Newton methods. Many well-known methods such as
limited-memory Broyden Family methods satisfy the general form. We
are able to prove several results about methods which satisfy the
general form. In particular, we show that the only limited-memory
Broyden Family method (using exact line searches) that is guaranteed
to terminate within n iterations on an n-dimensional strictly convex
quadratic is the limited-memory BFGS method. Furthermore, we are able
to introduce several new variations on the limited-memory BFGS method
that retain the quadratic termination property. We also have a new
result that shows that full-memory Broyden Family methods (using exact
line searches) that skip p updates to the quasi-Newton matrix will
terminate in no more than n+p steps on an n-dimensional strictly
convex quadratic. We propose several new variations on the
limited-memory BFGS method and test these on standard test problems.
We also introduce and test a new method for a process known as Latent
Semantic Indexing (LSI) for information retrieval. The new method
replaces the singular value matrix decomposition (SVD) at the heart of
LSI with a semi-discrete matrix decomposition (SDD). We show several
convergence results for the SDD and compare some strategies for
computing it on general matrices. We also compare the SVD-based LSI
to the SDD-based LSI and show that the SDD-based method has a faster
query computation time and requires significantly less storage. We
also propose and test several SDD-updating strategies for adding new
documents to the collection.