Large-Scale Manifold Learning
Venue
Computer Vision and Pattern Recognition (CVPR) (2008)
Publication Year
2008
Authors
Ameet Talwalkar, Sanjiv Kumar, Henry A. Rowley
BibTeX
Abstract
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.
