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

• URL: http://arxiv.org/abs/2608.04227v1
• Date: Tue, 04 Aug 2026 21:02:15 GMT
• Title: Random features for Grassmannian kernel approximation with bounded rank-one projections
• Abstract summary: We propose a family of random feature maps for scalable kernel machines on low-dimensional subspaces.<n>We show that inner products in the random feature space approximate well-defined rotation-invariant Grassmannian kernels.<n>Experiments on synthetic data and ETH-80 classification tasks show that these features accurately preserve Grassmannian geometry while reducing computation, memory, and storage.
• Score: 5.3340963304980535
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Implicit Manifold Gaussian Process Regression [49.0787777751317]
  Gaussian process regression is widely used to provide well-calibrated uncertainty estimates. It struggles with high-dimensional data because of the implicit low-dimensional manifold upon which the data actually lies. In this paper we propose a technique capable of inferring implicit structure directly from data (labeled and unlabeled) in a fully differentiable way.
  arXiv  Detail & Related papers  (2023-10-30T09:52:48Z)
• Tanimoto Random Features for Scalable Molecular Machine Learning [2.5112706394511766]
  We propose two kinds of novel random features to allow the Tanimoto kernel to scale to large datasets. We show that these random features are effective at approximating the Tanimoto coefficient of real-world datasets.
  arXiv  Detail & Related papers  (2023-06-26T16:11:11Z)
• A Multiple Parameter Linear Scale-Space for one dimensional Signal Classification [0.0]
  We construct a maximal set of kernels for a multi- parameter linear scale-space that allow us to construct trees for classification and recognition of one-dimensional continuous signals. A number of useful properties of the maximal set of kernels are derived. A new topologically invariant method of constructing trees is introduced.
  arXiv  Detail & Related papers  (2023-05-22T17:14:45Z)
• Random Smoothing Regularization in Kernel Gradient Descent Learning [24.383121157277007]
  We present a framework for random smoothing regularization that can adaptively learn a wide range of ground truth functions belonging to the classical Sobolev spaces. Our estimator can adapt to the structural assumptions of the underlying data and avoid the curse of dimensionality.
  arXiv  Detail & Related papers  (2023-05-05T13:37:34Z)
• Simplex Random Features [53.97976744884616]
  We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels. We show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.
  arXiv  Detail & Related papers  (2023-01-31T18:53:39Z)
• Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces I: the compact case [43.877478563933316]
  In to symmetries is one of the most fundamental forms of prior information one can consider. In this work, we develop constructive and practical techniques for building stationary Gaussian processes on a very large class of non-Euclidean spaces.
  arXiv  Detail & Related papers  (2022-08-31T16:40:40Z)
• Stochastic tensor space feature theory with applications to robust machine learning [3.6891975755608355]
  We develop a Multilevel Orthogonal Subspace (MOS) Karhunen-Loeve feature theory based on tensor spaces.<n>Our key observation is that separate machine learning classes can reside predominantly in mostly distinct subspaces.<n>Tests in the blood plasma dataset (Alzheimer's Disease Neuroimaging Initiative) show dramatic increases in accuracy.
  arXiv  Detail & Related papers  (2021-10-04T22:01:01Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
  We show that in the low-data regime $ND$, the Gram matrix can be decomposed in a manner that reduces the cost of inference to $mathcalO(N2D + (N2)3)$. We demonstrate this potential in a variety of tasks relevant for machine learning, such as optimization and Hamiltonian Monte Carlo with predictive gradients.
  arXiv  Detail & Related papers  (2021-02-15T13:24:41Z)
• Linear-time inference for Gaussian Processes on one dimension [17.77516394591124]
  We investigate data sampled on one dimension for which state-space models are popular due to their linearly-scaling computational costs. We provide the first general proof of conjecture that state-space models are general, able to approximate any one-dimensional Gaussian Processes. We develop parallelized algorithms for performing inference and learning in the LEG model, test the algorithm on real and synthetic data, and demonstrate scaling to datasets with billions of samples.
  arXiv  Detail & Related papers  (2020-03-11T23:20:13Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)
• Randomly Projected Additive Gaussian Processes for Regression [37.367935314532154]
  We use additive sums of kernels for GP regression, where each kernel operates on a different random projection of its inputs. We prove this convergence and its rate, and propose a deterministic approach that converges more quickly than purely random projections.
  arXiv  Detail & Related papers  (2019-12-30T07:26:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.