Finding an approximate mode of a Kernel density estimate

Jasper C.H. Lee, Jerry Li, Christopher Musco, Jeff M. Phillips, Wai Ming Tai

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Given points P = {p1,..., pn} subset of Rd, how do we find a point x which approximately maximizes the function n1 Ppi∈P e−∥pi−x2 ? 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(log3 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 log2 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.

    Original languageEnglish (US)
    Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
    EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959772044
    StatePublished - Sep 1 2021
    Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
    Duration: Sep 6 2021Sep 8 2021

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    ISSN (Print)1868-8969


    Conference29th Annual European Symposium on Algorithms, ESA 2021
    CityVitual, Lisbon


    • Coresets
    • Dimensionality reduction
    • Kernel density estimation
    • Means-shift

    ASJC Scopus subject areas

    • Software


    Dive into the research topics of 'Finding an approximate mode of a Kernel density estimate'. Together they form a unique fingerprint.

    Cite this