Low-Rank Isomap Algorithm
This work addresses a computational bottleneck in Isomap for researchers and practitioners in machine learning, offering an incremental improvement over existing methods.
The paper tackles the high computational complexity of Isomap, a nonlinear dimensionality reduction method, by proposing a low-rank algorithm that reduces complexity to linear order while preserving structural information, with experimental verification showing superiority in speed and accuracy on facial image clustering.
The Isomap is a well-known nonlinear dimensionality reduction method that highly suffers from computational complexity. Its computational complexity mainly arises from two stages; a) embedding a full graph on the data in the ambient space, and b) a complete eigenvalue decomposition. Although the reduction of the computational complexity of the graphing stage has been investigated, yet the eigenvalue decomposition stage remains a bottleneck in the problem. In this paper, we propose the Low-Rank Isomap algorithm by introducing a projection operator on the embedded graph from the ambient space to a low-rank latent space to facilitate applying the partial eigenvalue decomposition. This approach leads to reducing the complexity of Isomap to a linear order while preserving the structural information during the dimensionality reduction process. The superiority of the Low-Rank Isomap algorithm compared to some state-of-art algorithms is experimentally verified on facial image clustering in terms of speed and accuracy.