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.