Diffusion bases methods for segmentation and clustering

Abstract

Methods for dimensionality reduction of large data volumes, in particular hyper-spectral data cubes, include providing a dataset Γ of data points given as vectors, building a weighted graph G on Γ with a weight function w, wherein wcorresponds to a local coordinate-wise similarity between the coordinates in Γ; obtaining eigenvectors of a matrix derived from graph G and weight function w, and projecting the data points in Γ onto the eigenvectors to obtain a set of projection values Γfor each data point, whereby Γrepresents coordinates in a reduced space. In one embodiment, the matrix is constructed through the dividing each element of wby a square sum of its row multiplied by a square sum of its column. In another embodiment the matrix is constructed through a random walk on graph G via a Markov transition matrix P, which is derived from w. The reduced space coordinates are advantageously used to rapidly and efficiently perform segmentation and clustering.