> Detailanzeige

Lee, Jasper C.H. [VerfasserIn]; Li, Jerry [VerfasserIn]; Musco, Christopher [VerfasserIn]; Phillips, Jeff M. [VerfasserIn]; Tai, Wai Ming [VerfasserIn] ; Jasper C.H. Lee and Jerry Li and Christopher Musco and Jeff M. Phillips and Wai Ming Tai [MitwirkendeR]

Finding an Approximate Mode of a Kernel Density Estimate

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; Elektronischer Konferenzbericht; E-Artikel
  • Titel: Finding an Approximate Mode of a Kernel Density Estimate
  • Beteiligte: Lee, Jasper C.H. [VerfasserIn]; Li, Jerry [VerfasserIn]; Musco, Christopher [VerfasserIn]; Phillips, Jeff M. [VerfasserIn]; Tai, Wai Ming [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ESA.2021.61
  • Schlagwörter: Kernel density estimation ; Dimensionality reduction ; Means-shift ; Coresets
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.
  • Zugangsstatus: Freier Zugang