The GaussianSketch for Almost Relative Error Kernel Distance
The GaussianSketch for Almost Relative Error Kernel Distance
复制标题
DOI：
10.4230/lipics.approx/random.2020.12
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
J. M. Phillips;W. Tai
中科院分区：
文献类型：
--
作者：
J. M. Phillips;W. Tai
我们介绍了两个版本的将高斯核近似嵌入欧几里得内积空间的新草图。这些工作是通过截断高斯核的无限展开，并小心地调用递归tensorsketch [Ahle等人]。苏打2020]。在提供这些草图的集中和近似特性后，我们使用它们来近似点集之间的核距离。这些草图几乎产生$(1+\varepsilon)$ -相对误差，但有一个小的附加$\alpha$项。在第一种变体中，对$1/\alpha$的依赖是多对数的，但对原始维度$d$的多项式依赖程度更高。在第二种变体中，对$1/\alpha$的依赖仍然是多对数的，但对$d$的依赖是线性的。
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+\varepsilon)$-relative error, but with a small additive $\alpha$ term. In the first variants the dependence on $1/\alpha$ is poly-logarithmic, but has higher degree of polynomial dependence on the original dimension $d$. In the second variant, the dependence on $1/\alpha$ is still poly-logarithmic, but the dependence on $d$ is linear.