Fast ISOMAP Based on Minimum Set Coverage

摘要

Isometric feature mapping (ISOMAP) has two computational bottlenecks. The first is calculating the NxN graph distance matrix D_N . Using Floyd's algorithm, this is O(N~3)', this can be improved to O(kN~2 logN) by implementing Dijkstra's algorithm. The second bottleneck is the MDS eigenvalue calculation, which involves a full NxN matrix and has complexity O(N ~3). In this paper, we address both of these inefficiencies by a greedy approximation algorithm of minimum set coverage (MSC). The algorithm learns a minimum subset of overlapping neighborhoods for high dimensional data that lies on or near a low dimensional manifold. The new framework leads to order-of-magnitude reductions in computation time and makes it possible to study much larger problems in manifold learning.