2018/07/23 by Jubran, Ibrahim, Feldman, Dan
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.1807.08446
We suggest a new optimization technique for minimizing the sum ∑i=1n fi(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 Points-to-Lines alignment: Given n points p1,⋯,pn and n lines ℓ1,⋯,ℓn on the plane and z>0, compute the matching π:[n]→[n] and alignment (rotation matrix R and a translation vector t) that minimize the sum of Euclidean distances ∑i=1n dist(Rpi-t,ℓπ(i))z between each point to its corresponding line. This problem is non-trivial even if z=1 and the matching π is given. If π is given, the running time of our algorithms is O(n3), 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.