Collaborative Research: Spectral Graph Theory and Its Applications

合作研究：谱图理论及其应用

• 批准号: 0634957
• 负责人: Daniel Spielman
• 金额: --
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-05-01 至 2010-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0634957&HistoricalAwards=false
• 关键词: Collaborative; Research; Spectral; Graph; Theory

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.

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