Collaborative Research: Spectral Graph Theory and Its Applications

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

• 批准号: 0635357
• 负责人: Satish Rao
• 金额: $ 17.6万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-05-01 至 2010-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635357&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) 更好地估计费德勒值和广义费德勒值。应用开发： 1) 光谱图像分割的改进。 2）在数据挖掘和图像分割中使用广义特征值来组合多个信息源。 3）使用预处理器在图形模型中进行近似推理。4）将从光谱算法中获得的图像分割问题的见解与从最近的猴子视觉系统实验中获得的知识相结合，以更好地理解初级视觉皮层的功能。