title: Learning Markov Random Walks for robust subspace clustering and estimation.
abstract: Markov Random Walks (MRW) has proven to be an effective way to understand spectral clustering and embedding. However, due to less global structural measure, conventional MRW (e.g., the Gaussian kernel MRW) cannot be applied to handle data points drawn from a mixture of subspaces. In this paper, we introduce a regularized MRW learning model, using a low-rank penalty to constrain the global subspace structure, for subspace clustering and estimation. In our framework, both the local pairwise similarity and the global subspace structure can be learnt from the transition probabilities of MRW. We prove that under some suitable conditions, our proposed local/global criteria can exactly capture the multiple subspace structure and learn a low-dimensional embedding for the data, in which giving the true segmentation of subspaces. To improve robustness in real situations, we also propose an extension of the MRW learning model based on integrating transition matrix learning and error correction in a unified framework. Experimental results on both synthetic data and real applications demonstrate that our proposed MRW learning model and its robust extension outperform the state-of-the-art subspace clustering methods.
authors.affiliation: Dalian University of Technology, Dalian, China. Electronic address: rsliu0705@gmail.com.
authors.forename: Risheng
authors.initials: R
authors.lastname: Liu
authors.affiliation: Key Lab. of Machine Perception (MOE), School of EECS, Peking University, Beijing, China. Electronic address: zlin@pku.edu.cn.
authors.forename: Zhouchen
authors.initials: Z
authors.lastname: Lin
authors.affiliation: Dalian University of Technology, Dalian, China. Electronic address: zxsu@dlut.edu.cn.
authors.forename: Zhixun
authors.initials: Z
authors.lastname: Su
mesh_terms: D000465:Algorithms; D000818:Animals; D001185:Artificial Intelligence; D016000:Cluster Analysis; D004644:Emotions / Q000502:physiology*; D006801:Humans; D007858:Learning; D008032:Limbic System / Q000502:physiology; D008959:Models, Neurological; D008962:Models, Theoretical; D016571:Neural Networks, Computer; D010363:Pattern Recognition, Automated / Q000379:methods
keywords: Dimensionality reduction; Markov random walks; Spectral clustering; Subspace clustering and estimation; Transition probability learning