Signed random Fourier features for fast density estimation with indefinite kernels

Kernel density estimation (KDE) is one of the most fundamental statistical estimators of density functions. Its direct implementation on a dataset of $N$ points incurs an $\mathcal{O}(N^{2})$ computational cost, which is prohibitive for large-scale datasets. Kernel approximation techniques can be applied to bring the computational cost down to $\mathcal{O}(N)$. The random Fourier features (RFF) technique, based on sampling from the spectral density of the kernel function, has become popular to speed up kernel estimators for machine learning applications. Unfortunately, it is restricted to positive definite kernels, while the majority of kernel functions popular in KDE, such as the parabolic kernel, do not satisfy this property. To overcome this limitation, this article introduces the signed random Fourier features (SRFF) technique. It is a generalization of RFF compatible with indefinite kernels whose inverse Fourier transform is absolutely integrable. The motivation for introducing this method is to speed up KDE in the case of multivariate compact kernels, which are generally not positive definite. We detail how to implement SRFF for both product kernels and isotropic kernels. For the class of Kuttner-Golubov kernels $K(\boldsymbol{x}_{i},\boldsymbol{x}_{j})=(1-\left\Vert \boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\Vert ^α)^β\mathbf{1}_{\{\left\Vert \boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\Vert \leq1\}}$ where $\boldsymbol{x}_{i}\in\mathbb{R}^{d}$, $\boldsymbol{x}_{j}\in\mathbb{R}^{d}$, $α>0$, $β>0$, which includes the triangular, parabolic, biweight, triweight, and other kernel functions of interest for KDE as particular examples, we provide an explicit acceptance-rejection algorithm to sample from its signed spectral density. Our numerical tests on a dataset of one million points confirm the computational efficiency and accuracy of SRFF for large-scale KDE.

Real-Valued Hyperdimensional Sequence Representations with Hadamard Product Binding and Shift Equivariance

Encoding temporal order is a fundamental requirement for sequence representations in Hyperdimensional Computing. Fractional Power Encoding provides similarity-preserving position vectors whose inner products approximate shift-invariant kernels, and it supports shift-equivariant transformations of encoded sequence representations. However, standard formulations of Fractional Power Encoding are primarily designed for binding operations such as circular convolution or complex-valued multiplication, which limits their compatibility with Hadamard product binding of real-valued vectors. This paper develops real-valued position encodings motivated by Random Fourier Features, aiming to retain the desirable properties of Fractional Power Encoding while supporting Hadamard-based operations. We propose three real-valued position-encoding variants: a real-valued baseline based on the inverse Fourier transform, and Sinusoid and Cosine-only representations derived from Random Fourier Features. Among them, the Sinusoid variant provides an explicit algebraic shift operator, allowing temporal shifts to be applied directly to the vector-encoded sequence representation without re-encoding the shifted sequence. Experiments on time-series classification datasets show that the proposed real-valued representations achieve performance comparable to standard Fractional Power Encoding while enabling computationally efficient Hadamard product binding. The Sinusoid variant offers the most favorable trade-off, combining efficient real-valued implementation with exact shift-equivariant transformations.

Information-Based Exploration via Random Features for Reinforcement Learning

Representation learning has enabled classical exploration strategies to be extended to deep Reinforcement Learning (RL), but often makes algorithms more complex and theoretical guarantees harder to establish. We introduce Random Feature Information Gain (RFIG), grounded in Bayesian kernel methods theory, which uses random Fourier features to approximate information gain and compute exploration bonuses in non-countable spaces. We provide error bounds on information gain approximation and avoid the black-box aspects of neural network-based uncertainty estimation, for optimism-based exploration. We present practical details that make RFIG scalable to deep RL scenarios, enabling smooth integration into standard deep RL algorithms. Experimental evaluation across diverse control and navigation tasks demonstrates that RFIG achieves competitive performance with well-established deep exploration methods while offering superior theoretical interpretation.

Scalable and Differentiable Point-Cloud Registration Using Maximum Mean Discrepancy

We present MMD-Reg, a novel correspondence-free approach to point-cloud registration that is differentiable and has linear computational complexity in the number of points. We model registration as a nonlinear least-squares problem based on the Maximum Mean Discrepancy, approximated using random Fourier features. The resulting objective can be solved efficiently with standard methods such as Levenberg-Marquardt, and the solution is differentiable via the implicit function theorem. This allows MMD-Reg to be used as a differentiable optimization layer within end-to-end trainable models, supporting registration under challenging conditions such as poor initial alignment and partial overlap. We demonstrate this Neural MMD-Reg formulation by integrating the layer with a set transformer, training the resulting model in supervised and unsupervised settings, and comparing its performance against recent learning-based methods. We also evaluate standalone MMD-Reg, comparing its accuracy and scalability against widely used non-learning-based registration methods.