Collaborative Research: Spectral Graph Theory and Its Applications

谱图理论或代数图理论，也被称为，是研究图的特征值和特征向量与它们的组合性质之间的关系。图上的随机游走、扩展图、聚类和图的其他几个组合方面与它们的谱特性密切相关。最近的高维数据分析方法利用了数据的基本特征向量。这些数据集很大，并且不断增加，需要对给定查询进行“实时”准确的响应。这就需要非常快速的算法，同时也为它们的输出提供严格的理论保证。光谱技术已经被应用于图像处理，无论是计算机还是猴子的初级视觉皮层。所有这些应用的关键组成部分是算法的效率和精度保证求解这些线性系统，并找到他们的基本特征向量。一个由理论计算机科学家、机器学习科学家和神经科学家组成的多学科团队将开发和应用谱图理论，从数据挖掘到聚类和图像处理。开发的使能技术将包括：1)线性功或O（m log m）功算法，这些算法在多对数并行时间内运行，用于计算对角优势矩阵（包括拉普拉斯矩阵）的极值和广义特征值，以及用于解决相关线性系统的类似复杂性的算法。2) Fiedler值和广义Fiedler值的更好估计。应用发展：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.