Applied Computational Mathematics Division


Up

Sparse Low-Rank Approximations to Sparse Matrices

G. W. (Pete) Stewart
Information Technology Laboratory, Mathematical and Computational Sciences Division; and University of Maryland, Department of Computer Science

Wednesday, October 12, 2005 15:00-16:00,
NIST North (820), Room 145
Gaithersburg
Wednesday, October 12, 2005 13:00-14:00,
Room 4511
Boulder

Abstract: In many applications--latent semantic indexing, for example--it is required to obtain a reduced rank approximation to a sparse matrix X. Unfortunately, the approximations based on traditional decompositions, like the singular value and QR decompositions, are not in general sparse. In this talk, we will show how a variant of Gram-Schmidt orthogonalization, called the quasi-Gram-Schmidt method, can be used to compute a reduced rank approximation of the form YTZ, where Y consists of columns of X, Z consists of rows of X, and only T, which is of order of the rank of the approximation, is dense. In addition we will discuss the numerical stability of the quasi-Gram-Schmidt algorithm.

Speaker Bio: G. W. (Pete) Stewart received his degree in Mathematics in 1968 under the late Alston Householder. He has held academic positions at the University of Texas and Carnegie Mellon University. He is currently Full Professor in the Computer Science Department and is a permanent member of the Institute for Advanced Computer Studies at the University of Maryland, College Park. He is the author of over 125 journal articles on various aspects of numerical analysis and matrix computation, with applications in statistical computing, signal processing, and stochastic processes. His books include Introduction to Matrix Computation, Matrix Perturbation Theory (with J. G. Sun), Afternotes on Numerical Analysis, and Matrix Algorithms I and II--a survey of matrix computations. He is a coauthor of the LINPACK package for linear algebra. In 1999 he was awarded the Bauer Prize by the Technical University of Munich. He is a member of the National Academy of Engineering.

Presentation Slides: PDF

Contact: P. M. Ketcham

Note: Visitors from outside NIST must contact Robin Bickel; (301) 975-3668; at least 24 hours in advance.