The Eigenvalue Problem in Geometry and Combinatorial Optimization

本课题主要研究几何、组合优化和信息组织中的特征值问题。作为这项研究的一部分，将开发有效的算法来计算和逼近图论、计算几何、科学计算和互联网应用中出现的一大类矩阵的特征值和特征向量。我们将探讨以下主题。图划分的特征值/特征向量：主要的理论和算法问题是：如何正确地使用特征值/特征向量来找到图中可能的最佳划分，以及网格、平面图、有界亏格图和N体图等图的特征值的严格上界是什么。对这些问题的建设性回答可用于设计高效的图划分算法和软件。特征向量逼近的几何方法：主要目标是了解是否可以开发和使用几何方法来加快特征向量的逼近。许多图形，如平面图、有限元网格和最近邻域图，都带有几何特征。特征值问题在数据聚类和信息组织中的应用：目标是将谱图划分的工作与基于奇异值分解的数据聚类方法相关联，例如潜在语义索引(LSI)。这些术语文档矩阵的光谱技术在经验上取得了成功，但到目前为止还没有严格的数学解释。该项目希望通过扩展我们的光谱划分技术，为信息检索中的这些重要问题提供一个数学上合理的框架和有效的软件。

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.