基于有界秩一投影的Grassmannian核近似随机特征

# 具有有界秩一投影的格拉斯曼核逼近的随机特征
来源：https://arxiv.org/html/2608.04227
Rémi Delogne
[email protected]
INMA/ICTEAM, UCLouvain, 比利时
Laurent Jacques
[email protected]
INMA/ICTEAM, UCLouvain, 比利时

###### 摘要

我们提出了一族随机特征映射，用于在高维空间中的低维子空间（即格拉斯曼流形）上定义的可扩展核机器。这在数据类别或聚类能很好地由少数数据点的张成子空间表示时，在机器学习情境中尤为有用。经典的格拉斯曼核（如*投影核*或*Binet–Cauchy核*）在实际应用中需要构造完整的格拉姆矩阵，导致高维大子空间数据集的计算和内存成本高得令人望而却步。我们通过计算子空间的特定随机特征来弥补这一缺陷。这些特征将子空间投影矩阵的随机秩一投影与有界非线性变换（周期变换或二值变换）相结合，以驯服由此产生的重尾分布。我们证明，在随机特征空间中，内积能够逼近定义良好且旋转不变的格拉斯曼核，即仅依赖于所考虑子空间的主角的核。当随机特征数量远大于子空间内在维度时，我们表明该逼近以高概率对所有固定维数的子空间一致成立。当非线性变换为周期函数时，被逼近的核具有闭式表达式，其行为可调，能够在逆Binet–Cauchy型与高斯型机制之间架起桥梁，而二值化特征没有已知的闭式核，但更有利于构造紧凑的一位子空间特征。此外，我们还展示了如何利用基于随机化快速傅里叶变换的结构化秩一投影，在不牺牲实际实验精度的前提下进一步降低随机特征的计算复杂度。我们通过合成实验以及ETH-80数据集上的分类任务（表示不同视角下的视觉对象图像）来展示这些技术的实用性。所提出的随机特征能够以高精度恢复格拉斯曼几何，同时降低计算、内存和存储需求。这表明秩一嵌入为经典格拉斯曼核提供了一种实用且可扩展的替代方案。

## 1 引言

在许多有监督和无监督学习任务中，数据类别或聚类更适合用由特定类数据实例张成的低维*子空间*来表示。这一假设在多种情境中自然出现，例如图像与视频处理 (Watanabe and Pakvasa,1973 (https://arxiv.org/html/2608.04227#bib.bib48); Basri and Jacobs,2003 (https://arxiv.org/html/2608.04227#bib.bib43); Rao et al\.,2010 (https://arxiv.org/html/2608.04227#bib.bib45); Liu et al\.,2013 (https://arxiv.org/html/2608.04227#bib.bib44); Ji et al\.,2015 (https://arxiv.org/html/2608.04227#bib.bib25))、无线通信 (Schwarz and Tsiftsis,2021 (https://arxiv.org/html/2608.04227#bib.bib13))、动态子空间建模与信号处理 (Srivastava and Klassen,2004 (https://arxiv.org/html/2608.04227#bib.bib14); Saad-Falcon et al\.,2024 (https://arxiv.org/html/2608.04227#bib.bib20); Jayasumana et al\.,2015 (https://arxiv.org/html/2608.04227#bib.bib18))。这隐含着，我们不再处理欧几里得空间中的独立数据点，而是面对属于*格拉斯曼流形* \(\mathcal{G}(k,n)\) 的数据，即 \(\mathbb{R}^{n}\) 中所有 \(k\) 维子空间的集合。在有监督学习中，只要能够获得足够的训练数据，*核机器*（*例如*，SVM、回归 (Bach,2024 (https://arxiv.org/html/2608.04227#bib.bib5))）就可以借助适当正定的*核*——即在所有数据对之间计算并存储于*格拉姆矩阵*中的相似度得分——学习任意复杂的函数或分类边界。在格拉斯曼数据的情境下，存在大量用于量化格拉斯曼元素之间相似性的核（参见*例如* (Harandi et al\.,2014 (https://arxiv.org/html/2608.04227#bib.bib16)) 中的此类*核*列表），从而支持复杂的学习任务 (Hamm and Lee,2008 (https://arxiv.org/html/2608.04227#bib.bib35); Wolf and Shashua,2003 (https://arxiv.org/html/2608.04227#bib.bib52))。

尽管在理论上有效，核机器却面临可扩展性的缺陷。正如 Rahimi and Recht (2007 (https://arxiv.org/html/2608.04227#bib.bib34)) 所指出的，大型数据集（包含 \(N\) 个样本）需要处理一个 \(N\times N\) 的格拉姆矩阵，因此需要 \(\mathcal{O}(N^{2})\) 次（可能代价高昂的）核评估以及 \(\mathcal{O}(N^{2})\) 的内存成本。解决该问题的首要方法是近似格拉姆矩阵，例如通过 Nyström 方法进行低秩近似 (Drineas and Mahoney,2005 (https://arxiv.org/html/2608.04227#bib.bib55); Bach and Jordan,2005 (https://arxiv.org/html/2608.04227#bib.bib56))。这可将存储成本降低到 \(\mathcal{O}(mN)\)，其中 \(m\leqslant N\) 是所选样本的数量，但该方法仍是数据相关的，因为近似是从数据集中选取的样本构建的，并且仍需要对所有 \(N\) 个样本进行核评估。

*随机特征*提供了另一种直接逼近核的高效解决方案：每个数据点通过随机投影（可能结合非线性函数，*例如*周期函数、二值函数）嵌入到欧几里得空间中。在此空间中，随机特征之间的简单内积以受控误差逼近原始数据点对之间的特定核 (Rahimi and Recht,2007 (https://arxiv.org/html/2608.04227#bib.bib34))。对于格拉斯曼数据，压缩感知文献为我们提供了直接的随机特征构造方法 (Foucart,2016 (https://arxiv.org/html/2608.04227#bib.bib58); Candès and Plan,2011 (https://arxiv.org/html/2608.04227#bib.bib37))（见第3.1节 (https://arxiv.org/html/2608.04227#S3.SS1)）。我们可以通过将格拉斯曼数据向量化并投影到少数随机高斯矩阵上来嵌入它们，其数量随 \(\mathcal{G}(k,n)\) 的内在维度缩放 (Li and Gu,2018 (https://arxiv.org/html/2608.04227#bib.bib57))。然而，这种稠密高斯投影的成本使得该方法在计算和内存上都令人望而却步。

**主要贡献。** 在本工作中，我们提出了适用于格拉斯曼数据的新型随机特征。更具体地说，每个子空间 \(\mathcal{P}\in\mathcal{G}(k,n)\) 由其正交投影矩阵 \(\boldsymbol{P}=\boldsymbol{U}\boldsymbol{U}^{\top}\) 表示，并通过 \(m\) 个独立的秩一二次测量形式 \( \boldsymbol{a}_{i}^{\top}\boldsymbol{P}\boldsymbol{b}_{i} \) 来探测，其中 \(\boldsymbol{a}_{i},\boldsymbol{b}_{i}\sim_{\mathrm{i.i.d.}}\mathcal{N}(\textbf{0},\boldsymbol{I}_{n})\)。将这些测量堆叠起来定义了秩一投影（ROP）特征映射 \(\psi^{\,\mathrm{rop}}(\boldsymbol{U})=(\boldsymbol{a}_{i}^{\top}\boldsymbol{U}\boldsymbol{U}^{\top}\boldsymbol{b}_{i})_{i=1}^{m}\)，其经验内积是投影核的估计量，但具有重尾集中特性。为控制这一行为，我们将 \(\psi^{\,\mathrm{rop}}\) 与有界非线性函数复合。使用符号函数得到二值随机特征 \(\psi^{\scriptscriptstyle\pm}=\operatorname{sign}\circ\psi^{\,\mathrm{rop}}\)，其经验核 \(\widehat{\kappa}^{\,\scriptscriptstyle\pm}(\boldsymbol{U},\boldsymbol{V})=\frac{1}{m}\langle \psi^{\scriptscriptstyle\pm}(\boldsymbol{U}),\psi^{\scriptscriptstyle\pm}(\boldsymbol{V})\rangle\) 以高概率一致收敛到一个定义良好、正定且旋转不变的格拉斯曼核 \(\kappa^{\scriptscriptstyle\pm}\)，该核仅取决于两个子空间之间的*主角* (Conway et al\.,1996 (https://arxiv.org/html/2608.04227#bib.bib21); Harandi et al\.,2014 (https://arxiv.org/html/2608.04227#bib.bib16))。尽管 \(\kappa^{\scriptscriptstyle\pm}\) 没有已知的显式闭式形式，但我们证明它可以表示为相关投影矩阵 \(\boldsymbol{P}=\boldsymbol{U}\boldsymbol{U}^{\top}\) 和 \(\boldsymbol{Q}=\boldsymbol{V}\boldsymbol{V}^{\top}\) 的函数，即

\[
\kappa^{\scriptscriptstyle\pm}(\boldsymbol{U},\boldsymbol{V})=1-\frac{2}{\pi}\mathbb{E}\measuredangle(\boldsymbol{P}\boldsymbol{g},\boldsymbol{Q}\boldsymbol{g}),
\]

其中 \(\measuredangle(\boldsymbol{u},\boldsymbol{v})\) 是两个向量 \(\boldsymbol{u}\) 和 \(\boldsymbol{v}\) 之间的夹角，\(\boldsymbol{g}\sim\mathcal{N}(\textbf{0},\boldsymbol{I}_{n})\)。\(\kappa^{\scriptscriptstyle\pm}\) 的这种半显式刻画将使我们能够直观理解 \(\kappa^{\scriptscriptstyle\pm}\) 相对于子空间主角的行为。转而使用复指数则定义了周期随机特征 \(\psi^{\circ}=\exp({\sf i}\omega\,\psi^{\,\mathrm{rop}})\)，其期望核具有闭式形式

\[
\kappa^{\circ}(\boldsymbol{U},\boldsymbol{V})=\mathbb{E}\langle \psi^{\circ}(\boldsymbol{U}),\psi^{\circ}(\boldsymbol{V})\rangle=\prod_{j=1}^{k}\big(1+\omega^{2}\sin^{2}\theta_{j}\big)^{-1},
\]

其中 \(\{\theta_{j}\}_{j=1}^{k}\) 是 \(\boldsymbol{U}\) 和 \(\boldsymbol{V}\) 之间的主角。在两种情形下，我们都证明了随机特征的内积为目标核提供了无偏估计量，并且当 \(m=\mathcal{O}(kn)\)（忽略 \(\log\) 因子）时，在 \(\mathbb{V}(k,n)\)（\(\mathbb{R}^{n}\) 中 \(k\) 维标准正交基的集合）上满足一致逼近界，从而产生具有受控误差的可扩展格拉斯曼核近似。该过程如图1 (https://arxiv.org/html/2608.04227#S1.F1) 所示。

请注意，这些不同的特征映射各自逼近不同的核。稠密高斯投影和无界ROP针对的是投影核 \(\kappa^{\mathrm{p}}\)，而有界的二值ROP特征和周期ROP特征则分别诱导出不同的格拉斯曼核 \(\kappa^{\scriptscriptstyle\pm}\) 和 \(\kappa^{\circ}\)。除统计保证外，我们还评估了所提出随机特征构造的计算和内存效率。经典格拉斯曼核需要对 \(N\) 样本的格拉姆矩阵进行 \(\mathcal{O}(N^{2})\) 次核评估和存储，而投影矩阵的稠密随机嵌入每个特征需要 \(\mathcal{O}(n^{2})\) 的成本，所提出的基于有界ROP的特征可以在 \(\mathcal{O}(kmn)\) 次运算中计算，并使用 \(\mathcal{O}(mn)\) 内存存储。此外，第4.1节 (https://arxiv.org/html/2608.04227#S4.SS1) 和第4.2节 (https://arxiv.org/html/2608.04227#S4.SS2) 中建立的一致逼近结果说明，\(m=\mathcal{O}(kn)\) 个随机特征（忽略对数因子）就足以控制逼近误差，从而得到总体复杂度随环境维度线性增长的结果。我们进一步在第6节 (https://arxiv.org/html/2608.04227#S6) 中表明，通过借鉴 (Choromanski et al\.,2016 (https://arxiv.org/html/2608.04227#bib.bib79)) 的结构化随机变换替换高斯探测向量，可以显著降低这些成本，从而得到可在 \(\mathcal{O}(km\log n)\) 次运算中计算且存储需求大幅降低的特征映射。所有考虑方法的计算和内存复杂度详细对比见第5节 (https://arxiv.org/html/2608.04227#S5)，这些收益的实际影响在第8节 (https://arxiv.org/html/2608.04227#S8) 中通过实验加以说明。

> 图1：所提出方法的示意图。数据点被假定属于 \(\mathbb{R}^{n}\) 中的低维子空间。子空间由其标准正交基表示，然后嵌入到欧几里得空间中。该空间中的内积逼近定义良好的格拉斯曼核，从而能够高效地执行学习任务。

本文的其余部分组织如下。在第2节 (https://arxiv.org/html/2608.04227#S2) 中，我们首先提供导航 \(\mathcal{G}(k,n)\) 几何的基本工具，以及核机器随机特征构造的关键复习。在第3节 (https://arxiv.org/html/2608.04227#S3) 中，我们阐述了格拉斯曼元素线性随机特征的两种直接设计所遇到的局限性。在第4节 (https://arxiv.org/html/2608.04227#S4) 中，我们通过将线性秩一投影与有界非线性函数（即符号函数和周期虚指数函数）复合来给出这两种局限性的解决方案。我们提供了相应的二值和周期随机特征逼近特定格拉斯曼核的一致误差保证。我们在第6节 (https://arxiv.org/html/2608.04227#S6) 中详细讨论结构化随机特征方案，然后在第7节 (https://arxiv.org/html/2608.04227#S7) 中强调我们的方法如何与现有工作（如子空间分类的谱系）联系起来。我们最终在第8节 (https://arxiv.org/html/2608.04227#S8) 中展示我们的方法如何实现格拉斯曼数据的分类，然后得出结论。所有会妨碍阅读流畅性的技术证明都推迟到附录中。

##### 记号与约定

我们认为在此汇集本文使用的某些记号、概念和约定是有益的。由于我们面向总体复杂度分析，本工作中推导的许多界依赖于常数，记为 \(C,c,c',c'',\ldots>0\)，其值可能逐行变化。我们用粗体符号表示矩阵和向量，*例如* \(\boldsymbol{A}\in\mathbb{R}^{m\times n}\)，\(\boldsymbol{x}\in\mathbb{R}^{n}\)，而标量值用轻体符号表示。\(\mathbb{R}^{n}\) 中的单位矩阵为 \(\boldsymbol{I}_{n}\)。\(m\times n\) 零矩阵记为 \(\textbf{0}_{m\times n}\)，当上下文清楚时我们省略维度。两个向量 \(\boldsymbol{u}\) 和 \(\boldsymbol{v}\) 之间的夹角写作 \(\measuredangle(\boldsymbol{u},\boldsymbol{v})\)，\(\boldsymbol{u}\) 的 \(\ell_{2}\)-范数为 \(\|\boldsymbol{u}\|\)。\(\mathbb{R}^{n\times n}\) 中两个矩阵 \(\boldsymbol{A}\) 和 \(\boldsymbol{B}\) 的标量积为 \(\langle\boldsymbol{A},\boldsymbol{B}\rangle=\operatorname{tr}(\boldsymbol{A}^{\top}\boldsymbol{B})=\langle\operatorname{vec}(\boldsymbol{A}),\operatorname{vec}{\boldsymbol{B}}\rangle\)，其中 \(\operatorname{vec}{\boldsymbol{A}}\in\mathbb{R}^{n^{2}}\) 表示矩阵 \(\boldsymbol{A}\) 的向量化。相关的 Frobenius 范数