Collaborative Research: Spectral Graph Theory and Its Applications

谱图理论或称为代数图论，是研究图的特征值和特征向量之间的关系及其组合性质的学科。图上的随机游动、扩张图、聚类图和图的其他几个组合方面与它们的谱性质密切相关。最近分析高维数据的方法已经利用了数据的基本特征向量。这些数据集很大，而且不断增加，要求对给定的查询做出`实时‘准确的答复。这就产生了对非常快的算法的需求，这些算法也为它们的输出提供了严格的理论保证。光谱技术已经被应用于图像处理，无论是计算机还是猴子的初级视觉皮质。所有这些应用的关键组成部分是算法，它具有高效和准确的算法来求解这些线性系统并找到它们的基本特征向量。一个由理论计算机科学家、机器学习科学家和神经科学家组成的多学科团队将开发和应用谱图理论，从数据挖掘到聚类和图像处理。使能技术的发展将包括：1)在多对数并行时间内运行的线性工作或O(Mlogm)工作算法，用于计算对角占优矩阵的极值特征值和广义特征值，包括拉普拉斯矩阵，以及用于求解相关线性系统的类似复杂性的算法。2)菲德勒值和广义菲德勒值的更好估计。应用开发：1)改进光谱图像分割。2)在数据挖掘和图像分割中使用广义特征值来组合多个信息源。3)在图形模型中使用预条件算子进行近似推理。以及4)将从光谱算法中获得的对图像分割问题的见解与最近在猴子视觉系统中进行的实验中获得的知识相结合，以更好地了解初级视觉皮质的功能。

Spectral Graph Theory or Algebraic Graph Theory, as it is also known,is the study of the relationship between the eigenvalues andeigenvectors of graphs and their combinatorial properties. Randomwalks on graphs, expander graphs, clustering, and several othercombinatorial aspects of graphs are intimately connected to theirspectral properties. Recent approaches to the analysis ofhigh-dimensional data have exploited the fundamental eigenvectors ofthe data. These data sets are large and ever increasing requiring``real-time" accurate responses to the given queries. This creates theneed for very fast algorithms, that also provide strict theoreticalguarantees on their output. Spectral techniques have been applied to imageprocessing, both by computers and in the primary visual cortex ofmonkeys. Critical component to all these application is algorithmswith efficiency and accuracy guarantees for solving these linear systemand finding their fundamental eigenvectors.A multidisciplinary team consisting of Theoretical ComputerScientists, Machine Learning Scientist, and Neuroscientist willdevelop and apply spectral graph theory to applications from datamining to clustering, and image processing. Enabling technologydevelop will include: 1) linear-work or O(m log m)-work algorithmsthat run in poly-logarithmic parallel time for computing extremeeigenvalues and generalized eigenvalues of diagonally-dominantmatrices, including Laplacian matrices, as well as algorithms ofsimilar complexity for solving the related linear systems. 2) Betterestimates for Fiedler values and generalized Fiedler values.Application development: 1) Improvements in spectral imagesegmentation. 2) The use of generalized eigenvalues in data mining andimage segmentation to combine multiple sources of information. 3) Theuse of preconditioners for approximate inference in graphical models.and 4) Combine insights into the problem of image segmentation gainedfrom spectral algorithms with knowledge gained from recent experiments in visual systemof monkeys to better understand how the primary visual cortex functions.