Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Graph Laplacian eigenvectors form the core of many algorithms for representation, approximation, and compression of functions on graphs, with applications from image segmentation to shape analysis. Key to their utility is that they generalize the discrete cosine transform for regular lattices, and in the case of graphs formed from finite element discretization of a domain, approximate the continuous Neumann Laplacian eigenfunctions. However, graph Laplacians do not "feel" the directions in a digraph, and even modified Laplacians will give poor representation of the global structure. We will motivate and discuss the properties of graph distance matrices, which overcome these deficiencies. In one dimension, we obtain a relationship between the free-space and Neumann Green's functions, which through careful discretization, yields that appropriately modified graph distance eigenvectors also generalize the DCT for lattices. We'll conclude with current and future work toward establishing the distance matrix as both analytic and practical tool for mentioned and new applications. Joint work with Naoki Saito.