An empirical feature-based learning algorithm producing sparse approximations

A learning algorithm for regression is studied. It is a modified kernel projection machine (Blanchard et al., 2004 [2]) in the form of a least square regularization scheme with ℓ1-regularizer in a data dependent hypothesis space based on empirical features (constructed by a reproducing kernel and the learning data). The algorithm has three advantages. First, it does not involve any optimization process. Second, it produces sparse representations with respect to empirical features under a mild condition, without assuming sparsity in terms of any basis or system. Third, the output function converges to the regression function in the reproducing kernel Hilbert space at a satisfactory rate. Our error analysis does not require any sparsity assumption about the underlying regression function.