The graph based semi-supervised algorithm with ℓ1-regularizer

In this paper a new graph-based semi-supervised algorithm for regression problem is proposed. An excess generalization error bound is established. It evaluates the learning performance of the proposed method and has a fast convergence rate with O(lϵ−1)O(lϵ−1) decay. An example is given to show that the proposed method uses a small portion of the labeled and unlabeled data to represent the target function, which illustrates the sparsity of the algorithm, and can efficiently reduce the computational complexity of the semi-supervised learning. Moreover, some experiments are performed to validate the sparsity and learning performance of the formulation.