Spectral Graph Theory or Algebraic Graph Theory, as it is also known, is the study of the relationship between the eigenvalues and eigenvectors of graphs and their combinatorial properties. Random walks on graphs, expander graphs, clustering, and several other combinatorial aspects of graphs are intimately connected to their spectral properties. Recent approaches to the analysis of high-dimensional data have exploited the fundamental eigenvectors of the data. These data sets are large and ever increasing requiring ``real-time" accurate responses to the given queries. This creates the need for very fast algorithms, that also provide strict theoretical guarantees on their output. Spectral techniques have been applied to image processing, both by computers and in the primary visual cortex of monkeys. Critical component to all these application is algorithms with efficiency and accuracy guarantees for solving these linear system and finding their fundamental eigenvectors.
A multidisciplinary team consisting of Theoretical Computer Scientists, Machine Learning Scientist, and Neuroscientist will develop and apply spectral graph theory to applications from data mining to clustering, and image processing. Enabling technology develop will include: 1) linear-work or O(m log m)-work algorithms that run in poly-logarithmic parallel time for computing extreme eigenvalues and generalized eigenvalues of diagonally-dominant matrices, including Laplacian matrices, as well as algorithms of similar complexity for solving the related linear systems. 2) Better estimates for Fiedler values and generalized Fiedler values. Application development: 1) Improvements in spectral image segmentation. 2) The use of generalized eigenvalues in data mining and image segmentation to combine multiple sources of information. 3) The use of preconditioners for approximate inference in graphical models. and 4) Combine insights into the problem of image segmentation gained from spectral algorithms with knowledge gained from recent experiments in visual system of monkeys to better understand how the primary visual cortex functions.
