Diameter-Free Pointwise Gaussian KDE in Near-Additive Query Time
Wagner asked whether Gaussian kernel density estimation in $\mathbb R^d$ admits query time $\widetilde O(d+\varepsilon^{-2})$ without dependence on the diameter of the data. We answer this affirmatively for each fixed query: a randomized data structure answers a query to additive error $\varepsilon$ with probability $1-\delta$ in time $O((d+\varepsilon^{-2})\log(d+1)\log(2/\delta))$, independently of the number of data points and of their diameter. The key ingredient is a variance bound for a Fastfood-type structured Fourier block that holds uniformly in the norm of the displacement.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00272
curl -X POST /api/v1/records/hexagon/2610.00272/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00272/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'