文章基本信息

标题：The GaussianSketch for Almost Relative Error Kernel Distance
本地全文：下载
作者：Jeff M. Phillips ; Wai Ming Tai
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：12:1-12:20
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Kernel Distance; Kernel Density Estimation; Sketching