TY - GEN

T1 - A geometric perspective on dimensionality reduction

AU - Cai, Deng

AU - He, Xiaofei

AU - Han, Jiawei

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=73449132606&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73449132606&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:73449132606

SN - 9781615671090

T3 - Society for Industrial and Applied Mathematics - 9th SIAM International Conference on Data Mining 2009, Proceedings in Applied Mathematics

SP - 1417

EP - 1475

BT - Society for Industrial and Applied Mathematics - 9th SIAM International Conference on Data Mining 2009, Proceedings in Applied Mathematics 133

T2 - 9th SIAM International Conference on Data Mining 2009, SDM 2009

Y2 - 30 April 2009 through 2 May 2009

ER -