  Traditionally, kernel methods rely on the representer theorem which states
that the solution to a learning problem is obtained as a linear combination of
the data mapped into the reproducing kernel Hilbert space (RKHS). While elegant
from theoretical point of view, the theorem is prohibitive for algorithms'
scalability to large datasets, and the interpretability of the learned
function. In this paper, instead of using the traditional representer theorem,
we propose to search for a solution in RKHS that has a pre-image decomposition
in the original data space, where the elements don't necessarily correspond to
the elements in the training set. Our gradient-based optimisation method then
hinges on optimising over possibly sparse elements in the input space, and
enables us to obtain a kernel-based model with both primal and dual sparsity.
We give theoretical justification on the proposed method's generalization
ability via a Rademacher bound. Our experiments demonstrate a better
scalability and interpretability with accuracy on par with the traditional
kernel-based models.
