Abstract

We propose Spherical Structured Feature (SSF) maps to approximate shift and rotation invariant kernels as well as bth -order arc-cosine kernels (Cho & Saul, 2009). We construct SSF maps based on the point set on d - 1 dimensional sphere We prove that the inner product of SSF maps are unbiased estimates for above kernels if asymptotically uniformly distributed point set on is given. According to (Brauchart & Grabner, 2015), optimizing the discrete Riesz s-energy can generate asymptotically uniformly distributed point set on Sd?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.