用随机特征高效逼近流形核,降低计算开销。
Random features for Grassmannian kernel approximation with bounded rank-one projections

- 基于秩一投影与有界非线性变换构造随机特征
- 特征内积可近似旋转不变的流形核,保几何结构
- 适合大规模子空间数据,支持快速计算与存储
我们提出一类适用于低维子空间(即流形)上可扩展核机器的随机特征映射。当数据类别或聚类由少数样本张成时,此类表示尤为有效。经典流形核(如投影核与Binet-Cauchy核)需计算完整格拉姆矩阵,导致高维子空间大数据集的计算与内存开销巨大。本文通过子空间投影矩阵的随机秩一投影,结合周期性或二值化有界非线性变换,缓解此问题。结果表明,随机特征空间中的内积能良好逼近仅依赖子空间主角的旋转不变流形核。当特征数量相对于子空间内在维度足够大时,该近似在所有固定维子空间上以高概率一致成立。周期变换下,近似核具有闭式表达,可调参介于逆Binet-Cauchy与高斯型之间;二值变换生成紧凑的一比特子空间特征,虽无闭式核。基于随机快速傅里叶变换的结构化秩一投影进一步降低计算量而不损失实际精度。合成数据与ETH-80分类任务实验表明,该方法准确保留流形几何,同时显著降低计算、内存与存储需求。秩一嵌入因此为经典流形核提供了一种实用且可扩展的替代方案。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。