Ofir Pele: "Interpolated Discretized Embedding of Single Objects and Object Pairs for Classification, Semi Metric Learning and Distance Approximation"

We present a method for the approximation and learning of arbitrary continuous distance functions and semimetrics. Previous work have been limited to Euclidean metrics or other families of metrics (e.g., the Earth Mover's Distance). One usage of this method is to learn a function that given two objects returns whether they match (e.g., descriptor matching learning). Another usage is directly learning a distance function (e.g., perceptual color difference learning). The method can also be used for approximation of distances and for single object classification or regression tasks. The time complexity of computing the distance function is relatively efficient: $O(n\log(nc))$, where n is the dimension of the input vectors and c is a parameter that determines the distance function complexity.