Sparse Geodesic Paths

In this paper we propose a new distance metric for signals that admit a sparse representation in a known basis or dictionary. The metric is derived as the length of the sparse geodesic path between two points, by which we mean the shortest path between the points that is itself sparse. We show that the distance can be computed via a simple formula and that the entire geodesic path can be easily generated. The distance provides a natural similarity measure that can be exploited as a perceptually meaningful distance metric for natural images. Furthermore, the distance has applications in supervised, semi-supervised, and unsupervised learning settings.