title: Learning with l1-graph for image analysis.
abstract: The graph construction procedure essentially determines the potentials of those graph-oriented learning algorithms for image analysis. In this paper, we propose a process to build the so-called directed l1-graph, in which the vertices involve all the samples and the ingoing edge weights to each vertex describe its l1-norm driven reconstruction from the remaining samples and the noise. Then, a series of new algorithms for various machine learning tasks, e.g., data clustering, subspace learning, and semi-supervised learning, are derived upon the l1-graphs. Compared with the conventional k-nearest-neighbor graph and epsilon-ball graph, the l1-graph possesses the advantages: (1) greater robustness to data noise, (2) automatic sparsity, and (3) adaptive neighborhood for individual datum. Extensive experiments on three real-world datasets show the consistent superiority of l1-graph over those classic graphs in data clustering, subspace learning, and semi-supervised learning tasks.
authors.affiliation: Department of Electrical and Computer Engineering, National University of Singapore, Singapore. chengbin@nus.edu.sg
authors.forename: Bin
authors.initials: B
authors.lastname: Cheng
authors.forename: Jianchao
authors.initials: J
authors.lastname: Yang
authors.forename: Shuicheng
authors.initials: S
authors.lastname: Yan
authors.forename: Yun
authors.initials: Y
authors.lastname: Fu
authors.forename: Thomas S
authors.initials: TS
authors.lastname: Huang