NUMERICAL LINEAR ALGEBRA IN DATA EXPLORATION

CSci 8363 -- Spring 2005

Linear Algebra has contributed many methods for handling very large quantities of numerical data. Here we examine many of these linear algebra methods and how they have been applied to the exploration and analysis of very large data collections. Part of the class will be an overview of many of the linear algebra methods for large sparse matrix problems such as eigenvalue and singular value problems. But the bulk of the class will be devoted to how these linear algebra methods have been used in information retrieval, data mining, unsupervised clustering, and the like. Examples of methods we will examine are Latent Semantic Indexing, Linear Least Squares Fit, Principal Direction Divisive Partitioning, Hubs and Authorities Analysis, Support Vector Machines, and recent ideas on non-negative matrix decompositions. A collection of basic research papers, some of a tutorial nature, will be used for the class. Examples will be taken from vision recognition systems, biological gene analysis, document retrieval.

Prerequisites and Work Plan

Students should be familiar with basic linear algebra concepts and methods such as Gaussian elimination for systems of linear equations. Exposure to concepts such as matrix eigenvalues and matrix least squares problems will be very useful, but we will review the principal numerical methods used to solve them. We will also review the concepts and methods from information retrieval, pattern recognition, and machine learning as the topics are encountered in class. Students will be expected to read a research paper and/or do a project, with some results presented in class.

• Latent Semantic Indexing.
  Represent a large text document collection with a bag-of-words model, and then find a nearby representation with fewer degrees of freedom, replacing individual words with ``concepts''.
• Linear Least Squares Fit.
  Find the best mapping from a Term Frequency Matrix (bag-of-words model) to a ``Concept Frequency Matrix'' for use in information retrieval.
• Spectral Learning
  Use techniques drawn from spectral graph partitioning and Markov chains to extract clusters using a mix of labelled and unlabelled data.
• Principal Direction Divisive Parititoning.
  A scalable, but deterministic, unsupervised clustering method.
• Hubs and Authorities.
  Use the link structure inherent in web pages to expose those sites many pages point to (the Authorities) and those sites pointing to many pages (the Hubs). This idea is the basis for some more effective search engines like Google, and also used for analyzing computer networks.
• Support Vector Machines.
  Find hyperplanes which not only separate the data points (e.g. documents in a bag-of-words model), but which maximize the separate from hyperplane to cluster contents.
• Information Theoretic Clustering and Matrix Analysis
  Discuss recent proposals for a non-negative matrix factorization, for finding a reduced order representation for a data matrix based on information theoretic considerations, including entropy, mutual information and Bregman divergences.
• Wavelets.
  Wavelets are a popular way to view signal data in many resolutions, for data compression, noise removal, information extraction. How do wavelets work, from a linear algebra perspective. Compare to other methods for multiresolution and frequency analysis

For Further Information

Contact Daniel Boley, 6-209 EE/CS Bldg, boley@cs.umn.edu, 625-3887.http://www-users.cs.umn.edu/~boley