Scalable sparse approximation of a sample mean

We examine the problem of approximating the mean of a set of vectors as a sparse linear combination of those vectors. This problem is motivated by a common methodology in machine learning where a probability distribution is represented as the sample mean of kernel functions. In applications where this kernel mean function is evaluated repeatedly, having a sparse approximation is essential for scalability. However, existing sparse approximation algorithms such as matching and basis pursuit scale quadratically in the sample size, and are therefore not well suited to this problem for large sample sizes. We introduce an approximation bound involving a novel incoherence measure, and propose bound minimization as a sparse approximation strategy. In the context of sparsely approximating a kernel mean function, the bound is efficiently minimized by solving an appropriate instance of the k-center problem, and the resulting algorithm has linear complexity in the sample size.