No-Trick (Treat) Kernel Adaptive Filtering using Deterministic Features
  Kernel methods form a powerful, versatile, and theoretically-grounded
unifying framework to solve nonlinear problems in signal processing and machine
learning. The standard approach relies on the kernel trick to perform pairwise
evaluations of a kernel function, which leads to scalability issues for large
datasets due to its linear and superlinear growth with respect to the training
data. A popular approach to tackle this problem, known as random Fourier
features (RFFs), samples from a distribution to obtain the data-independent
basis of a higher finite-dimensional feature space, where its dot product
approximates the kernel function. Recently, deterministic, rather than random
construction has been shown to outperform RFFs, by approximating the kernel in
the frequency domain using Gaussian quadrature. In this paper, we view the dot
product of these explicit mappings not as an approximation, but as an
equivalent positive-definite kernel that induces a new finite-dimensional
reproducing kernel Hilbert space (RKHS). This opens the door to no-trick (NT)
online kernel adaptive filtering (KAF) that is scalable and robust. Random
features are prone to large variances in performance, especially for smaller
dimensions. Here, we focus on deterministic feature-map construction based on
polynomial-exact solutions and show their superiority over random
constructions. Without loss of generality, we apply this approach to classical
adaptive filtering algorithms and validate the methodology to show that
deterministic features are faster to generate and outperform state-of-the-art
kernel methods based on random Fourier features.
