Learning with ℓ₁-graph for image analysis

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 ℓ₁-graph, in which the vertices involve all the samples and the ingoing edge weights to each vertex describe its ℓ₁;-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 ℓ₁-graphs. Compared with the conventional k-nearest-neighbor graph and ε-ball graph, the ℓ₁-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 ℓ₁ -graph over those classic graphs in data clustering, subspace learning, and semi-supervised learning tasks.