Signed random Fourier features for fast density estimation with indefinite kernels
Abstract
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 𝒪(N2) computational cost, which is prohibitive for large-scale datasets. Kernel approximation techniques can be applied to bring the computational cost down to 𝒪(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(xi,xj)=(1−‖ xi−xj‖ α)β1{‖ xi−xj‖ ≤1} where xi∈ℝd, xj∈ℝ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.
Related
- A data-driven Fourier-mixture neural-network method for density estimation
- Positive kernels in Lie group representations and Fourier interpolation
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- Model-assisted estimation of the finite population mean via local linear regression with associated kernels
- On the Sequentially Semiseparable Structure of SDE-Induced Kernels and Efficient Algorithms for Kernel-Based Estimation Problems
BibTeX
@misc{wang2026signed,
title = {{Signed random Fourier features for fast density estimation with indefinite kernels}},
author = {Xie Wang and Nicolas Langrené and Wen Chen},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29265},
eprint = {2608.29265},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29265},
}
RIS
TY - UNPB
TI - Signed random Fourier features for fast density estimation with indefinite kernels
AU - Xie Wang
AU - Nicolas Langrené
AU - Wen Chen
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2608.29265
UR - https://arxiv.org/abs/2608.29265
AB - 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 𝒪(N^2) computational cost, which is prohibitive for large-scale datasets. Kernel approximation techniques can be applied to bring the computational cost down to 𝒪(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(x_i,x_j)=(1−‖ x_i−x_j‖ ^α)^β1_{‖ x_i−x_j‖ ≤1} where x_i∈ℝ^d, x_j∈ℝ^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.
ER -