The Eigenvalue Problem in Geometry and Combinatorial Optimization

点击翻译按钮获取中文摘要

This project focuses on the study of the eigenvalue problem in geometry, combinatorial optimization, and information organization. As part of this research, efficient algorithms will be developed for computing and approximating eigenvalues and eigenvectors of a large class of matrices that arise in graph theory, computational geometry, scientific computing, and Internet applications. The following topics will be investiagated. Eigenvalues/eigenvectors for graph partitioning: The main theoretical and algorithmic questions are: how to properly use eigenvalues/eigenvectors to find the best possible partition in a graph, and what is a tight upper bound on the eigenvalue for graphs such as meshes, planar graphs, bounded genus graphs and N-body graphs. Constructive answers to these questions can be used to design efficient algorithms and software for graph partitioning.Geometric methods for eigenvector approximation: The primary goal is to understand whether geometry methods can be developed and used to speed up the approximation of eigenvectors. Many graphs such as planar graphs, finite element meshes, and nearest neighborhood graphs come with a geometric characterization. One can use their geometric structures in the solution and approximation of the eigenvalue problem.Applications of the eigenvalue problem to data clustering and information organization: The objective is to relate the work on spectral graph partitioning to the singular value decomposition based method for data clustering, such as the Latent Semantic Indexing (LSI). These spectral techniques for term-document matrices has enjoyed empirical success, but had heretofore been without rigorous mathematical explanation. The project is expected, by extending our techniques for spectral partitioning, to provide a mathematically sound framework and efficient software for these important problems in information retrieval.