Algorithms for Lipschitz Learning on Graphs
| Autor: | Kyng, R., Rao, A., Sushant Sachdeva, Spielman, D. A. |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Scopus-Elsevier |
| DOI: | 10.48550/arxiv.1505.00290 |
| Popis: | 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 $\widetilde{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 $\widetilde{O} (m^{3/2})$. Comment: Code used in this work is available at https://github.com/danspielman/YINSlex 30 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|