License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.61
URN: urn:nbn:de:0030-drops-146428
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14642/
Lee, Jasper C.H. ;
Li, Jerry ;
Musco, Christopher ;
Phillips, Jeff M. ;
Tai, Wai Ming
Finding an Approximate Mode of a Kernel Density Estimate
Abstract
Given points P = {p₁,...,p_n} subset of ℝ^d, how do we find a point x which approximately maximizes the function 1/n ∑_{p_i ∈ P} e^{-‖p_i-x‖²}? In other words, how do we find an approximate mode of a Gaussian kernel density estimate (KDE) of P? Given the power of KDEs in representing probability distributions and other continuous functions, the basic mode finding problem is widely applicable. However, it is poorly understood algorithmically. We provide fast and provably accurate approximation algorithms for mode finding in both the low and high dimensional settings. For low (constant) dimension, our main contribution is a reduction to solving systems of polynomial inequalities. For high dimension, we prove the first dimensionality reduction result for KDE mode finding. The latter result leverages Johnson-Lindenstrauss projection, Kirszbraun’s classic extension theorem, and perhaps surprisingly, the mean-shift heuristic for mode finding. For constant approximation factor these algorithms run in O(n (log n)^{O(d)}) and O(nd + (log n)^{O(log³ n)}), respectively; these are proven more precisely as a (1+ε)-approximation guarantee. Furthermore, for the special case of d = 2, we give a combinatorial algorithm running in O(n log² n) time. We empirically demonstrate that the random projection approach and the 2-dimensional algorithm improves over the state-of-the-art mode-finding heuristics.
BibTeX - Entry
@InProceedings{lee_et_al:LIPIcs.ESA.2021.61,
author = {Lee, Jasper C.H. and Li, Jerry and Musco, Christopher and Phillips, Jeff M. and Tai, Wai Ming},
title = {{Finding an Approximate Mode of a Kernel Density Estimate}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {61:1--61:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14642},
URN = {urn:nbn:de:0030-drops-146428},
doi = {10.4230/LIPIcs.ESA.2021.61},
annote = {Keywords: Kernel density estimation, Dimensionality reduction, Coresets, Means-shift}
}
|
Keywords: |
|
Kernel density estimation, Dimensionality reduction, Coresets, Means-shift |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
