Collaborative Research: Spectral Graph Theory and Its Applications

点击翻译按钮获取中文摘要

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.