Algorithms for Lipschitz Learning on Graphs

Authors Rasmus Kyng, Anup B. Rao, Sushant Sachdeva, Daniel A. Spielman

Publication date 1 May 2015

Has companion code repository https://github.com/danspielman/YINSlex

Abstract: We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large

p

of

p

-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time

w i d e t i l d e O (m n)

. The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform

l_{0}

-regularization on the given values in polynomial time and

l_{1}

-regularization on the initial function values and on graph edge weights in time

w i d e t i l d e O (m^{3 / 2})

.

This page was built for publication: Algorithms for Lipschitz Learning on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6261424)