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

Taha Bouhsine

cs.LGJun 8, 2026

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

Authors: Taha Bouhsine

Organizations: Azetta AI

Abstract

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

Explore similar work

Aug 4, 2026cs.LG

Random features for Grassmannian kernel approximation with bounded rank-one projections

We propose a family of random feature maps for scalable kernel machines on low-dimensional subspaces, ie on the Grassmannian manifold. Such representations are useful when data classes or clusters are well described by the span of a few samples. Classical Grassmannian kernels, including the projection and Binet-Cauchy kernels, require full Gram matrices, which leads to prohibitive computational and memory costs for large high-dimensional subspace datasets. We address this limitation using random features based on rank-one projections of subspace projection matrices followed by bounded non-linear transforms, either periodic or binary, to control the resulting distributions. We show that inner products in the random feature space approximate well-defined rotation-invariant Grassmannian kernels that depend only on the principal angles between subspaces. When the number of features is sufficiently large relative to the intrinsic subspace dimension, the approximation holds uniformly over all fixed-dimensional subspaces with high probability. For periodic transforms, the approximated kernel has a closed-form expression with tunable behaviour between inverse Binet-Cauchy and Gaussian-type regimes. Binary transforms yield compact one-bit subspace features, although no closed-form kernel is known. Structured rank-one projections based on randomised fast Fourier transforms further reduce computation without sacrificing practical accuracy. Experiments on synthetic data and ETH-80 classification tasks show that these features accurately preserve Grassmannian geometry while reducing computation, memory, and storage. Rank-one embeddings therefore provide a practical and scalable alternative to classical Grassmannian kernels.

Rémi Delogne, Laurent Jacques

Reproducing Kernel Hilbert Spaces Low-Rank Factorization

Ask PDF

Sep 3, 2026math.NA

Spectral Convergence of Random Feature Method in Multiple Dimensions

We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes. The analysis establishes general high-probability approximation estimates in the interpolation scale generated by a kernel integral operator. On a single event determined only by the sampled features, one random space approximates every target in a prescribed source ball; moreover, for each target, a single coefficient vector defines an approximant that attains spectral accuracy simultaneously in all admissible error norms. For both regularity-adapted frequency distributions and uniform distributions on growing frequency windows, the resulting rates range from super-exponential to algebraic, depending on the regularity of the target. Second, we establish abstract error estimates for strong- and weak-form RFM discretizations, thereby converting the preceding approximation bounds into convergence estimates for multidimensional second-order elliptic boundary value and eigenvalue problems. Finally, for random feature matrices (RFMtxs), we prove super-exponential singular-value decay with Fourier features and exponential decay with

\tanh

features, together with corresponding condition-number lower bounds. The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.

Pingbing Ming, Hao Yu

Regularity Spectral Algorithms Optimization Convergence Analysis Singular Value Decomposition

Ask PDF

May 25, 2026cs.LG

Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding

Conditionally positive definite (CPD) kernels are defined with respect to a function class

\mathcal{F}

. It is well known that such a kernel

K

is associated with its native space (defined analogously to an RKHS), which in turn gives rise to a learning method -- called conditional kernel ridge regression (conditional KRR) due to its analogy with KRR -- where the estimated regression function is penalized by the square of its native space norm. This method is of interest because it can be viewed as classical linear regression, with features specified by

\mathcal{F}

, followed by the application of standard KRR to the residual (unexplained) component of the target variable. Methods of this type have recently attracted increasing attention. We study the statistical properties of this method by reducing its behavior to that of KRR with another fixed kernel, called the residual kernel. Our main theoretical result shows that such a reduction is indeed possible, at the cost of an additional term in the expected test risk, bounded by

\mathcal{O}(1/\sqrt{N})

, where

N

is the sample size and the hidden constant depends on the class

\mathcal{F}

and the input distribution. This reduction enables us to analyze conditional KRR in the case where

K

is positive definite and

\mathcal{F}

is given by the first

k

principal eigenfunctions in the Mercer decomposition of

K

. We also consider the setting where

\mathcal{F}

consists of

k

random features from a random feature representation of

K

. It turns out that these two settings are closely related. Both our theoretical analysis and experiments confirm that conditional KRR outperforms standard KRR in these cases whenever the

\mathcal{F}

-component of the regression function is more pronounced than the residual part.

Rustem Takhanov, Zhenisbek Assylbekov

Kernel Ridge Regression Regression Largest Eigenvalue Multilevel Image Thresholding

Ask PDF