In this talk, we'll present fast algorithms for some interpolation problems on graphs. Given real-valued observations on some of the vertices, our goal is to compute a smooth (Lipschitz) extension to all vertices. Our focus will be the absolutely minimal Lipschitz extension, which is the limit of p-Laplacian regularization for large p.

We present algorithms to compute a minimal Lipschitz extension in expected linear time, and to compute an absolutely minimal Lipschitz extension in expected O(mn) time. We have implemented variants of the latter algorithm that run on graphs with millions of edges in a few minutes. Our algorithms naturally extend to directed graphs. We'll present some experimental results for detecting spam webpages using our algorithms.

Finally, we'll discuss how these extensions are particularly suited for regularization: We'll present an algorithm for l_1 regularization on the input in O(m^(3/2)) time. We'll also give a poly-time algorithm for l_0 regularization (outlier removal), which is surprising since outlier removal is NP-hard for other natural extensions.

This is joint work with Rasmus Kyng, Anup Rao, and Daniel Spielman.