Sparse Approximation of a Kernel Mean

DOI10.1109/TSP.2016.2628353zbMATH Open1414.94146arXiv1503.00323OpenAlexW2964181129MaRDI QIDQ4620657FDOQ4620657

Authors: Efrén Cruz Cortés, Clayton Scott 

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: Kernel means are frequently used to represent probability distributions in machine learning problems. In particular, the well known kernel density estimator and the kernel mean embedding both have the form of a kernel mean. Unfortunately, kernel means are faced with scalability issues. A single point evaluation of the kernel density estimator, for example, requires a computation time linear in the training sample size. To address this challenge, we present a method to efficiently construct a sparse approximation of a kernel mean. We do so by first establishing an incoherence-based bound on the approximation error, and then noticing that, for the case of radial kernels, the bound can be minimized by solving the $k$-center problem. The outcome is a linear time construction of a sparse kernel mean, which also lends itself naturally to an automatic sparsity selection scheme. We show the computational gains of our method by looking at three problems involving kernel means: Euclidean embedding of distributions, class proportion estimation, and clustering using the mean-shift algorithm.

Full work available at URL: https://arxiv.org/abs/1503.00323

Recommendations

• Approximation Bounds for Some Sparse Kernel Regression Algorithms
• Sparse Representation With Kernels
• The kernel semi-least squares method for sparse distance approximation
• scientific article; zbMATH DE number 1843055
• Sparsity in multiple kernel learning
• Approximate kernel partial least squares
• Kernel estimators for the mean function of a stochastic process under sparse design conditions
• Sparse kernel partial least squares regression.

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (4)

• Title not available (Why is that?)
• Greedy Kernel Approximation for Sparse Surrogate Modeling
• Near-optimal coresets of kernel density estimates
• An efficient sum query algorithm for distance-based locally dominating functions

This page was built for publication: Sparse Approximation of a Kernel Mean

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620657)