Speaker: Alfred Hero, University of Michigan
Abstract: Many big data applications involve difficult combinatorial optimization that can be cast as finding a minimal graph that covers a subset of data points. Examples include computing minimal spanning trees over visual features in computer vision, finding a shortest path over an image database between image pairs, or detecting non-dominated anti-chains in multi-objective database search. When the nodes are real-valued random vectors and the graph is constructed on the basis of Euclidean distance these minimal paths can have continuum limits as the number of nodes approaches infinity. Such continuum limits can lead to low complexity diffusion approximations to the solution of the associated combinatorial problem. We will present theory and application of continuum limits and illustrate how such limits can break the combinatorial bottleneck in large scale data analysis.