Spherical Structured Feature Maps for Kernel Approximation

Abstract

We propose Spherical Structured Feature (SSF) maps to approximate shift and rotation invariant kernels as well as b^th-order arc-cosine kernels (Cho \& Saul, 2009). We construct SSF maps based on the point set on d-1 dimensional sphere S^d-1. We prove that the inner product of SSF maps are unbiased estimates for above kernels if asymptotically uniformly distributed point set on S^d-1 is given. According to (Brauchart \& Grabner, 2015), optimizing the discrete Riesz s-energy can generate asymptotically uniformly distributed point set on S^d-1. Thus, we propose an efficient coordinate decent method to find a local optimum of the discrete Riesz s-energy 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.

Tasks

Reproductions