A geometric perspective on dimensionality reduction

Deng Cai, Xiaofei He, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSociety for Industrial and Applied Mathematics - 9th SIAM International Conference on Data Mining 2009, Proceedings in Applied Mathematics 133
Pages1417-1475
Number of pages59
StatePublished - Dec 1 2009
Externally publishedYes
Event9th SIAM International Conference on Data Mining 2009, SDM 2009 - Sparks, NV, United States
Duration: Apr 30 2009May 2 2009

Publication series

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

Other

Other9th SIAM International Conference on Data Mining 2009, SDM 2009
Country/TerritoryUnited States
CitySparks, NV
Period4/30/095/2/09

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Software
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A geometric perspective on dimensionality reduction'. Together they form a unique fingerprint.

Cite this