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.

众所周知，光谱图理论或代数图理论是对图形和它们组合特性的特征值和它们之间的关系的研究。图形，扩展器图，聚类和图形的其他几个combinatorial方面的随机步行密切连接到其光谱属性。 对高维数据分析的最新方法利用了数据的基本特征向量。这些数据集很大且不断增加，需要对给定查询的准确响应。这是为非常快速的算法而创建的，这也为其输出提供了严格的理论保证。频谱技术都应用于ImageProcorpers，均通过计算机应用。在所有这些应用的主要视觉皮层中。从数据固定到群集的应用程序和图像处理。 Laplacian矩阵以及用于求解相关线性系统的类似复杂性的算法。 2）对于Fiedler值和普遍的Fiedler值。应用开发：1）光谱成像的改进。 2）在数据挖掘和图像分割中使用广义特征值以结合多个信息来源。 3）在图形模型中使用预处理以进行近似推断。4）结合对图像分割问题的见解，从光谱算法获得的图像分割问题以及从猴子视觉系统的最新实验中获得的知识，以更好地理解主要的视觉皮质的功能。