Research map / Learning theory and algorithms / Kernels and regression theory

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

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: RKHS kernel methods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes random features for Grassmannian kernels built from bounded (sign or periodic) transforms of random rank-one projections of subspace projectors, with uniform approximation guarantees and fast structured (Hadamard) variants.

Problem

Kernel machines on Grassmannian data (subspaces) require N x N Gram matrices with O(N^2) cost; dense random projections of projectors are costly in memory and computation, and unbounded rank-one projection features have heavy tails preventing uniform guarantees.

Approach

Compose random rank-one projections a_i^T P b_i with bounded nonlinearities: the sign function gives binary features whose expected kernel is a rotation-invariant Grassmannian kernel (no closed form for k>1), and the complex exponential gives periodic features with closed-form kernel prod_j (1+omega^2 sin^2 theta_j)^{-1}; structured Hadamard-based probes reduce cost to O(km log n).

Key results

• Periodic features with omega and binary features approximate their target Grassmannian kernels uniformly over G(k,n) with m=O(kn log factors) features, with error bound delta.
• Structured Hadamard-based ROP features reduce computation to O(delta^-2 k^2 n log n) and storage to O(delta^-2 k^2 n) without losing accuracy in experiments.
• k=1 binary kernel has closed form (1-2theta/pi)^2.

Surprising findings

• Unbounded rank-one projection features are argued to require m=O((kn)^2) for uniform guarantees over all subspaces, unlike bounded features.

Limitations

• No closed form for the binary kernel when k>1.
• Uniform bounds are worst-case over G(k,n) and may be loose for structured subsets of subspaces.
• Experiments limited to synthetic tests and ETH-80 classification.

Experimental setup

Datasets: ETH-80

Benchmarks: ETH-80

Metrics: kernel approximation error classification accuracy runtime memory

Baselines: dense Gaussian random projections projection kernel Binet-Cauchy kernel unbounded rank-one projection features

Builds on: random Fourier features rank-one projections projection kernel Binet-Cauchy kernel Fastfood / structured Hadamard projections

Closest papers by meaning

• Recycling Randomness with Structure for Sublinear time Kernel Expansions (ICML 2016 · similarity 0.88)
• Quadrature-based features for kernel approximation (NeurIPS 2018 · similarity 0.88)
• Manifold Random Features (NeurIPS 2026 · similarity 0.87)
• On The Relative Error of Random Fourier Features for Preserving Kernel Distance (ICLR 2023 · similarity 0.87)
• Random Features for Shift-Invariant Kernels with Moment Matching (AAAI 2017 · similarity 0.87)
• Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling (ICML 2020 · similarity 0.87)