Spherical Structured Feature Maps for Kernel Approximation
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:22562264, 2017.
Abstract
We propose Spherical Structured Feature (SSF) maps to approximate shift and rotation invariant kernels as well as $b^{th}$order arccosine kernels (Cho \& Saul, 2009). We construct SSF maps based on the point set on $d1$ dimensional sphere $\mathbb{S}^{d1}$. We prove that the inner product of SSF maps are unbiased estimates for above kernels if asymptotically uniformly distributed point set on $\mathbb{S}^{d1}$ is given. According to (Brauchart \& Grabner, 2015), optimizing the discrete Riesz senergy can generate asymptotically uniformly distributed point set on $\mathbb{S}^{d1}$. Thus, we propose an efficient coordinate decent method to find a local optimum of the discrete Riesz senergy for SSF maps construction. Theoretically, SSF maps construction achieves linear space complexity and loglinear time complexity. Empirically, SSF maps achieve superior performance compared with other methods.
Related Material


