Skip navigation

Spectral Methods, Approximation Theory, and the Analysis of Graphs and Networks: New Tools for Very Large Data Sets

Event Date: April 7, 2008
Speaker: Patrick J. Wolfe
Speaker Affiliation: Harvard University
Sponsor: CNSIP Area Seminar
Time: 2:00 PM
Location: EE 118
Contact Name: Prof. Charles Bouman
Contact Phone: 765-494-0340
Contact Email:

Spectral methods are of fundamental importance in statistics and machine learning, as they underlie algorithms from classical principal components analysis to more recent approaches that exploit manifold structure.  In most cases, the core technical problem can be reduced to computing a low-rank approximation to a positive-definite kernel.  Motivated by such applications, we first present here two new algorithms for the approximation of positive semi-definite kernels, together with error bounds that improve upon results in the literature. The first of these—based on sampling—leads to a randomized algorithm whereupon the kernel induces a probability distribution on its set of partitions, whereas the latter approach—based on sorting—provides for the selection of a partition in a deterministic way.  We then turn to the discovery of structure in random network topologies.  Though traditional models have well-established asymptotic properties and admit straightforward simulation techniques, they often fail to describe properties of observed random networks, such as constraints on node linkages.  In such scenarios, exact simulation in a way that respects the underlying measure rapidly becomes difficult, and fewer large-sample limits are known.  We demonstrate new hypothesis tests for graph structure in such cases, and apply them to the problem of "community detection" in large graphs--a task closely related to spectral clustering.  We give estimates of the power of this test for several possible models of topological structure.


Patrick J. Wolfe received a B.S. in Electrical Engineering and a B.Mus. concurrently from the University of Illinois at Urbana-Champaign in 1998, both with honors. He then earned his Ph.D. in Engineering from the University of Cambridge (UK) as a National Science Foundation Graduate Research Fellow, working on the application of perceptual criteria to statistical audio signal processing.  Prior to founding the Statistics and Information Sciences Laboratory at Harvard in 2004, Professor Wolfe held a Fellowship and College Lectureship jointly in Engineering and Computer Science at New Hall, a University of Cambridge constituent college where he also served as Dean.  He has also taught in the Department of Statistical Science at University College, London, and continues to act as a consultant to the professional audio community.  In addition to his diverse teaching activities, Professor Wolfe has published in the literatures of engineering, computer science, and statistics, and has received honors from the IEEE, the Acoustical Society of America, and the International Society for Bayesian Analysis.  His research group focuses on statistical signal processing and its application to tasks involving modern high-dimensional data sets, in particular sounds, images, and networks.