Signed random Fourier features for fast density estimation with indefinite kernels

Xie Wang; Nicolas Langrené; Wen Chen

stat.COAug 29, 2026

Signed random Fourier features for fast density estimation with indefinite kernels

Authors: Xie Wang, Nicolas Langrené, Wen Chen

Organizations: Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK · Guangdong Provincial/Zhuhai Key Laboratory of Interdisciplinary Research and Application for Data Science, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China.

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 $\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.

Figures & tables

Kernel name	$\alpha$	$\beta$	Formula
Triangular	$1$	$1$	$K(\boldsymbol{u})=(1-\left\\|\boldsymbol{u}\right\\|)\mathbbm{1}_{\{\left\\|\boldsymbol{u}\right\\|\leq 1\}}$
Parabolic	$2$	$1$	$K(\boldsymbol{u})=(1-\left\\|\boldsymbol{u}\right\\|^{2})\mathbbm{1}_{\{\left\\|\boldsymbol{u}\right\\|\leq 1\}}$
Biweight	$2$	$2$	$K(\boldsymbol{u})=(1-\left\\|\boldsymbol{u}\right\\|^{2})^{2}\mathbbm{1}_{\{\left\\|\boldsymbol{u}\right\\|\leq 1\}}$
Triweight	$2$	$3$	$K(\boldsymbol{u})=(1-\left\\|\boldsymbol{u}\right\\|^{2})^{3}\mathbbm{1}_{\{\left\\|\boldsymbol{u}\right\\|\leq 1\}}$
Tricube	$3$	$3$	$K(\boldsymbol{u})=(1-\left\\|\boldsymbol{u}\right\\|^{3})^{3}\mathbbm{1}_{\{\left\\|\boldsymbol{u}\right\\|\leq 1\}}$

Table 1: Examples of kernel functions included in the Kuttner-Golubov class ( 21 )

Panel of Figure 1 — Figure 1: Proposal densities for the spectral radius densities proportional to $r^{d-1}\left|\mathfrak{f}(r)\right|$ of the triangular kernel (left: $d=1$ , right: $d=2$ ).

Panel of Figure 2 — Figure 2: Proposal densities for the spectral radius densities proportional to $r^{d-1}\left|\mathfrak{f}(r)\right|$ of the parabolic kernel (left: $d=1$ , right: $d=2$ ).

Panel of Figure 3 — Figure 3: Proposal densities for the spectral radius densities proportional to $r^{d-1}\left|\mathfrak{f}(r)\right|$ of the triweight kernel (top left: $d=1$ , top right: $d=2$ , bottom left: $d=4$ , bottom right: $d=6$ ).

Panel of Figure 4 — Figure 4: Proposal densities for the truncated spectral radius densities proportional to the positive part $\max(f(r),0)$ (left) and the negative part $\max(-f(r),0)$ (right) of the inverse Fourier transform of the univariate parabolic kernel. To be compared to Figure 2 (left).

Figure 5: Univariate triangular kernel and its random Fourier features approximation ( 12 ) using $M=1000$ random projections.

Figure 6: Bivariate triangular kernel (left) and its signed random Fourier features approximation ( 14 ) (right) using $M=4000$ random projections.

Figure 7: Univariate parabolic kernel and its signed random Fourier features approximation ( 14 ) using $M=1000$ random projections.

Figure 8: Bivariate parabolic kernel (left) and its signed random Fourier features approximation ( 14 ) (right) using $M=4000$ random projections.

Figure 9: Univariate triweight kernel and its signed random Fourier features approximation ( 14 ) using $M=1000$ random projections.

Figure 10: Bivariate triweight kernel (left) and its signed random Fourier features approximation ( 14 ) (right) using $M=4000$ random projections.

Panel of Figure 11 — Figure 11: Mean absolute error of SRFF with respect to $M$ (left: $d=1$ , right: $d=2$ ).

Panel of Figure 12 — Figure 12: Runtime comparison between direct KDE and SRFF KDE with respect to the number of random features $M$ (left: $d=1$ , right: $d=2$ ).

Kernel Density Estimation

Kernel density estimation is a nonparametric method for estimating probability distributions by smoothing observed samples with kernels.

See all 13 papers

Random Fourier Features in Near-Linear Time
Oct 10, 2026Sepideh Mahabadi, Sandeep Silwal, Tal WagnerRandom Feature Methods Fourier Feature Embeddings
Microsoft Research – Redmond · University of Wisconsin-Madison · Tel Aviv University
Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization
Jun 8, 2026Taha BouhsineFourier Feature Embeddings Kernel Ridge Regression
Azetta AI
On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning
Oct 13, 2026Caixing WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University, Nanjing, China

Oct 10, 2026J/K move · Enter open · S save

Random Fourier Features in Near-Linear Time

Sepideh Mahabadi, Sandeep Silwal, Tal Wagner

Microsoft Research – Redmond · University of Wisconsin-Madison · Tel Aviv University

Random Feature Methods Fourier Feature Embeddings Kernel Methods

Open paper AskPDF arXiv

Random Fourier features approximate a shift-invariant kernel in

\mathbb{R}^d

, such as the Gaussian kernel

\exp(-\tfrac12\|x-y\|_2^2)

, using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating

m

such features requires

O(md)

time. A long line of work on structured random features has accelerated this computation for the Gaussian kernel and other radial kernels, albeit with weaker concentration guarantees. We close this gap by showing a random feature map that can be computed in near-linear time

O((d+m)\log d)

and yields near-subgaussian concentration. We obtain it through a new and tighter analysis of the Fastfood feature map of Le, Sarlós and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.

Abstract

Kernel Density Estimation

Explore similar work

Random Fourier Features in Near-Linear Time

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning