Aligning Points to Lines: Provable Approximations
| Autor: | Ibrahim Jubran, Dan Feldman |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Polynomial (hyperelastic model)
Discrete mathematics Computational Geometry (cs.CG) FOS: Computer and information sciences Computer Science - Machine Learning Computer science Approximation algorithm Context (language use) Machine Learning (stat.ML) Computational geometry Computer Science Applications Machine Learning (cs.LG) Computational Theory and Mathematics Statistics - Machine Learning Euclidean geometry Line (geometry) Convex optimization Piecewise Computer Science - Computational Geometry Information Systems |
| DOI: | 10.48550/arxiv.1807.08446 |
| Popis: | We suggest a new optimization technique for minimizing the sum $\sum_{i=1}^n f_i(x)$ of $n$ non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-time is polynomial in $n$ for the fundamental problem of \emph{Points-to-Lines alignment}: Given $n$ points $p_1,\cdots,p_n$ and $n$ lines $\ell_1,\cdots,\ell_n$ on the plane and $z>0$, compute the matching $\pi:[n]\to[n]$ and alignment (rotation matrix $R$ and a translation vector $t$) that minimize the sum of Euclidean distances $\sum_{i=1}^n \mathrm{dist}(Rp_i-t,\ell_{\pi(i)})^z$ between each point to its corresponding line. This problem is non-trivial even if $z=1$ and the matching $\pi$ is given. If $\pi$ is given, the running time of our algorithms is $O(n^3)$, and even near-linear in $n$ using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g. outliers or pseudo-distances such as $M$-estimators for the problem are also provided. Experimental results and open source code show that our provable algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|