Learning spectral embedding via iterative eigenvalue thresholding

Abstract

Learning data representation is a fundamental problem in data mining and machine learning. Spectral embedding is one popular method for learning effective data representations. In this paper we propose a novel framework to learn enhanced spectral embedding, which not only considers the geometrical structure of the data space, but also takes advantage of the given pairwise constraints. The proposed formulation can be solved by an iterative eigenvalue thresholding (IET) algorithm. Specially, we convert the problem of learning spectral embedding with pairwise constraints into the one of completing an "ideal" kernel matrix. And we introduce the spectral embedding of graph Laplacian as the auxiliary information and cast it as a small-scale positive semidefinite (PSD) matrix optimization problem with nuclear norm regularization. Then, we develop an IET algorithm to solve it efficiently. Moreover, we also present an effective semi-supervised clustering (SSC) approach with learned spectral embedding (LSE). Finally, we validate the proposed IET algorithm and LSE approach by extensive experiments on real-world data sets. © 2012 ACM.