Large-Scale Manifold Learning

This paper examines the problem of extracting low-dimensional manifold structure given millions of high-dimensional face images. Specifically, we address the computational challenges of nonlinear dimensionality reduction via Isomap and Laplacian Eigenmaps, using a graph containing about 18 million nodes and 65 million edges. Since most manifold learning techniques rely on spectral decomposition, we first analyze two approximate spectral decomposition techniques for large dense matrices (Nystrom and Column-sampling), providing the first direct theoretical and empirical comparison between these techniques. We next
show extensive experiments on learning low-dimensional
embeddings for two large face datasets: CMU-PIE (35
thousand faces) and a web dataset (18 million faces). Our
comparisons show that the Nystrom approximation is superior
to the Column-sampling method. Furthermore, approximate
Isomap tends to perform better than Laplacian
Eigenmaps on both clustering and classification with the
labeled CMU-PIE dataset.

• Machine Perception