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

Oct 10, 2026

Random Fourier Features in Near-Linear Time

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.

Sepideh Mahabadi, Sandeep Silwal, Tal Wagner

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

Random Feature Methods Fourier Feature Embeddings Kernel Methods

Ask PDF

Jun 8, 2026

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

Bernstein--Schur kernels are products of a finite-feature kernel and a completely monotone shift-invariant kernel: nonstationary kernels falling between the shift-invariant and dot-product templates random features exploit, so neither Bochner sampling nor polynomial sketching applies to the full kernel directly. We give one random-feature construction for the whole class that randomizes both factors: it sketches the finite modulation and samples the radial factor's one-dimensional Bernstein--Widder scale before applying Gaussian random Fourier features, giving feature dimension

Dm

, free of the

O(d^2)

size of the exact modulation feature. With the modulation kept exact (the

m\to\infty

limit), we prove unbiasedness, an exact variance, and a matrix-Bernstein operator-norm bound controlled by the top kernel and modulation eigenvalues and an intrinsic dimension rather than the crude

N\max_{ij}

route. Whitening this argument at the ridge makes the effective dimension

d_{\mathrm{eff}}(λ)

the exact intrinsic dimension of the matrix variance, so

O((1+\|P\|_{\mathrm{op}}/λ)\log(d_{\mathrm{eff}}/δ))

radial draws preserve the kernel-ridge solution; tilting the draw by a closed-form whitened leverage improves this to the effective-dimension count

O((1+d_{\mathrm{eff}})\log(d_{\mathrm{eff}}/δ))

. Conditioning on the sketch carries every guarantee to the deployed doubly-randomized estimator up to one additive sketch term, and all hold for the whole class with the modulation Gram in place of the polynomial one. The flagship instance is the biased

yat

-kernel

k_{yat,b}(w,x)=(w^\top x+b)^2/(\|w-x\|^2+\varepsilon)

, whose family span contains the inverse-multiquadric kernel by finite differences in

b

Taha Bouhsine

Azetta AI

Fourier Feature Embeddings Kernel Ridge Regression Randomized Sketching Random Feature Methods Kernel Methods

Ask PDF

Oct 13, 2026

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

Random features provide a standard approach to scaling kernel methods to large datasets by approximating the kernel with a finite-dimensional feature map. Existing works of random feature methods primarily focus on well-specified models and light-tailed noise conditions, leaving a gap in understanding their performance under more general conditions, such as misspecified models and heavy-tailed noise. In this paper, we provide a comprehensive and improved analysis of kernel ridge regression with random features (KRR-RF) under general conditions. In the light-tailed noise setting, we improve upon the worst-case uniform bounds of the feature map used in the previous works and lead to the minimax optimal learning rates with

2r+γ>α_0

, where

(r,γ,α_0)

denote the regularity of the target function, the effective dimension of the kernel, and the embedding index of the RKHS, respectively. In the heavy-tailed noise setting, we leverage a recently developed Hilbert-valued Fuk-Nagaev inequality and extend the same optimal results under finite weak moment conditions. The additional cost to achieve robustness is a mildly stronger explicit sample-size requirement than in the light-tailed case. For both settings, our results recover the conditions random features budgets (up to log factors) required in the previous works. In the most benign case when

α_0=γ

, KRR-RF are minimax optimal for all

r \in (0,1]

. To the best of our knowledge, this is the first work to establish optimal learning rates for KRR-RF under weak moment conditions in the misspecified setting. Numerical experiments and a real data analysis validate the derived learning rates and demonstrate their practical relevance in the presence of mis-specification and heavy-tailed noise.

Caixing Wang

School of Statistics and Data Science, Southeast University, Nanjing, China

Random Feature Methods Kernel Ridge Regression Statistical Learning Theory Model Misspecification

Ask PDF

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