2026-07-26T17:28:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12615 2024-03-06T10:51:15Z ddc:004 open_access

The GaussianSketch for Almost Relative Error Kernel Distance Phillips, Jeff M. Tai, Wai Ming Kernel Distance Kernel Density Estimation Sketching We introduce two versions of a new sketch for approximately embedding the Gaussian kernel into Euclidean inner product space. These work by truncating infinite expansions of the Gaussian kernel, and carefully invoking the RecursiveTensorSketch [Ahle et al. SODA 2020]. After providing concentration and approximation properties of these sketches, we use them to approximate the kernel distance between points sets. These sketches yield almost (1+ε)-relative error, but with a small additive α term. In the first variants the dependence on 1/α is poly-logarithmic, but has higher degree of polynomial dependence on the original dimension d. In the second variant, the dependence on 1/α is still poly-logarithmic, but the dependence on d is linear. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff M. Phillips and Wai Ming Tai 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.12 urn:nbn:de:0030-drops-126150 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode