2009 IEEE International Conference on
Systems, Man, and Cybernetics |
Abstract
In this article we establish a connection between semi-supervised learning and compressive sampling. We show that sparsity and compressibility of the learning function can be obtained from heavy-tailed distributions of filter responses or coefficients in spectral decompositions. In many cases the NP-hard problems of finding sparsest solutions can be replaced by $l^1$-problems from convex optimisation theory, which provide effective tools for semi-supervised learning. We present several conjectures and examples.