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_ix‖²}? 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 JohnsonLindenstrauss projection, Kirszbraun’s classic extension theorem, and perhaps surprisingly, the meanshift 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 2dimensional algorithm improves over the stateoftheart modefinding 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:161:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14642},
URN = {urn:nbn:de:0030drops146428},
doi = {10.4230/LIPIcs.ESA.2021.61},
annote = {Keywords: Kernel density estimation, Dimensionality reduction, Coresets, Meansshift}
}
Keywords: 

Kernel density estimation, Dimensionality reduction, Coresets, Meansshift 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 