Name
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 $\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})$. |
Year | Venue | DocType |
|---|---|---|
2015 | COLT | Journal |
Volume | Citations | PageRank |
abs/1505.00290 | 7 | 0.71 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rasmus Kyng | 1 | 56 | 9.00 |
| Anup Rao | 2 | 123 | 17.38 |
| Sushant Sachdeva | 3 | 171 | 16.90 |
| Daniel A. Spielman | 4 | 4257 | 638.57 |