  Nonlinear dimensionality reduction methods have demonstrated top-notch
performance in many pattern recognition and image classification tasks. Despite
their popularity, they suffer from highly expensive time and memory
requirements, which render them inapplicable to large-scale datasets. To
leverage such cases we propose a new method called "Path-Based Isomap". Similar
to Isomap, we exploit geodesic paths to find the low-dimensional embedding.
However, instead of preserving pairwise geodesic distances, the low-dimensional
embedding is computed via a path-mapping algorithm. Due to the much fewer
number of paths compared to number of data points, a significant improvement in
time and memory complexity without any decline in performance is achieved. The
method demonstrates state-of-the-art performance on well-known synthetic and
real-world datasets, as well as in the presence of noise.
