A geometric perspective on dimensionality reduction

How can we detect low dimensional structures from high dimensional data? This problem is usually referred to as dimensionality reduction and has received a lot of interests in many fields of information processing, including data mining, information retrieval, and pattern recognition. Over the past few decades, a large family of algorithms - supervised or unsupervised; stemming from statistics or from geometry theory - have been proposed to provide different solutions to this problem. Despite the different motivations of these algorithms, we will present in this tutorial a common graph embedding framework which unifies many of the existing algorithms. In this framework, the dimensionality reduction algorithms can be considered as either direct graph embedding or its linear/kernel extension by using an intrinsic graph that describes certain geometric properties of a data set. This tutorial is aimed to complement the tutorial given by Lawrence Saul at NIPS 2005 on "Spectral Methods for Dimensional Reduction". Saul's tutorial mainly covers the algorithms that are direct graph embedding approaches. However, direct graph embedding only provides the embedding results of training samples. With linear/kernel extension, we are able to obtain an embedding function which is defined everywhere. Some approaches that can efficiently learn the embedding function will also be discussed.