一种低复杂度的隐式稠密草图方法

《Information and Computation》：An implicit dense sketching with lower complexity

　　

摘要

随机草图（Random sketching）在随机线性代数中发挥着关键作用。尽管传统的稠密草图方法，如高斯草图或Rademacher草图，具有出色的稳定性，但其计算成本仍然很高，具体而言，将一个n维向量草图到k维空间需要O(nk)的时间。为解决这一局限性，本文提出了一种高效且稳定的稠密草图算法。所提出的草图矩阵是隐式生成的，能够仅以$O(n+k^2)$的时间和空间复杂度，将一个n维向量嵌入到k维空间中。当$k\le O\left(\sqrt{n}\right)$时，这转化为线性的O(n)复杂度。由于其隐式生成和稠密结构，该算法被称为隐式稠密草图（Implicit Dense Sketching, IDS）。除了计算效率之外，我们的理论分析还建立了矩阵元素的成对独立性、期望意义下的范数保持性、方差界，以及 oblivious 子空间嵌入、低秩逼近和近似矩阵乘法的保证。为展示其实际应用价值，我们将IDS应用于随机化奇异值分解（RSVD）、流式数据的单遍RSVD以及基于草图最小二乘解的随机化Arnoldi过程。在这三个应用上的数值实验一致表明，IDS算法的性能优于现有的最先进方法。

引言

随机草图是一种将高维向量投影到低维空间的同时保持其基本几何性质的技术，它是众多随机化线性代数应用的基石 [1], [2]。由于其重要的实际意义，近年来开发高效且稳定的随机草图技术吸引了大量研究关注 [3], [4]。需要注意的是，随机草图也被称为随机嵌入；在本工作中这两个术语含义相同。

对于许多随机化线性代数应用，随机草图是降低问题维度和加速整体计算过程的基本工具。以奇异值分解（SVD）为主要例子。当数据维度扩展到数百万或数十亿时，经典SVD算法的计算时间和内存开销变得难以承受。为缓解这一瓶颈，随机化SVD（RSVD）利用随机草图将高维数据投影到显著更低维的子空间中，然后再进行分解 [3], [5], [6], [7], [8]。另一个典型例子是Arnoldi过程，它被广泛用于计算特征值/特征向量或求解大规模线性系统。对于海量数据集，已提出了一种高效的基于草图的随机化Arnoldi过程 [9]，其中原始的高维最小二乘问题通过随机草图被转化为低维问题。因此，草图矩阵的效率直接决定了这些下游求解器的整体性能，这意味着加速随机草图有可能加速一大类相关算法。

高斯草图或许是最流行的草图方法 [10], [11], [12], [13], [14]。它具有卓越的稳定性，被广泛认为是最自然的随机投影技术 [5]。因此，高斯草图经常用于RSVD框架中。Rademacher草图是另一种广泛使用的方法 [15], [16]，其草图性能与高斯草图相当。这两种方法都属于稠密草图的范畴，通常表现出比稀疏草图算法更优越的实际稳定性。然而，稠密草图的主要瓶颈在于其高昂的计算复杂度，需要将一个n维向量投影到k维空间需要O(nk)的时间。

为了提高计算效率，快速变换技术和各种稀疏草图算法已被提出 [3], [5], [17], [18], [19], [20]。例如，部分子采样随机Hadamard变换（P-SRHT）利用快速Hadamard变换实现了加速。对于基于此类快速变换的草图算法，单次草图操作的典型时间复杂度降低到O(nlog?n)或O(nlog?k)。另一种突出的方法是稀疏符号草图 [17], [18], [19]，其中CountSketch算法 [21]是一个具有最高稀疏度的特例。文献 [17], [18], [19], [21] 中已经建立了稀疏符号草图的全面理论分析。然而，当目标维度k较小时，CountSketch在实际场景中可能会遭受严重性能下降 [3], [5]，这一弱点也是超稀疏随机草图算法所共有的 [22]。

近年来，对有效和加速草图算法的进一步探索引起了大量研究关注。例如，文献 [3] 中提出了一种改进的稀疏符号草图，将单次草图操作的时间复杂度降低到O(n)。同时，文献 [20] 中建立了欧几里得空间中降维所需时间的非平凡下界——当嵌入不限于稀疏草图时。与现有的稠密替代方法相比，稀疏草图由于其结构稀疏性而具有更高的计算效率。然而，这种稀疏结构固有的限制了其处理包含少量主导元素（即重击者）的高维向量或平滑输入相干性的能力。因此，稠密草图能否被加速到具有可比效率同时保持其出色的稳定性，仍然是一个重要的开放性问题。

为应对这一挑战，本工作旨在设计一种高效且同时保持出色稳定性的稠密草图算法。本文的主要贡献如下：

• •
  我们提出了隐式稠密草图（IDS）算法。通过隐式生成稠密草图矩阵，IDS能够仅以$O(n+k^2)$的时间和空间复杂度，将一个n维向量嵌入到k维空间中。
• •
  我们提出了对IDS的全面理论分析，建立了其计算复杂度、草图结果的期望和方差，以及 oblivious 子空间嵌入、近似矩阵乘法和低秩逼近的严格保证。
• •
  我们将所提出的IDS算法部署于RSVD框架、单遍RSVD变体和随机化Arnoldi过程中。大量数值实验表明，IDS算法在实际应用中的性能优于现有的最先进方法。

所提出的IDS的源代码公开可用，地址为 https://github.com/CBYFTS/An-Implicit-Dense-Sketching-with-Lower-Complexity。

章节摘要

背景

在本节中，我们回顾了最广泛采用的随机草图方法。为了便于算法描述的可读性，我们在本文中采用了MATLAB风格的索引表示法。例如，h_{1: j,1: j}表示由前j行和前j列组成的子矩阵。除非另有说明，‖?·?‖表示?₂范数（或矩阵的谱范数），而‖?·?‖_F表示Frobenius范数。

随机草图的主要目标是将一个

隐式稠密草图

在本节中，我们提出了隐式稠密草图（IDS）算法。我们首先介绍IDS背后的核心思想，然后正式展示整体算法。最后，我们建立并证明了IDS的理论性质和保证。

数值实验

为了评估所提出的IDS算法的有效性和效率，我们将其应用于三个下游任务：随机化SVD（RSVD）、流式数据的单遍RSVD以及随机化Arnoldi过程。在整个实验过程中，超参数固定为$\xi =2$、$\zeta =2$和$\omega =2$，这意味着扩展的草图维度为$k^{\prime }=2k$。

RSVD实验在一台配备13代Intel Core i5-13500H处理器（2.6 GHz）的工作站上使用MATLAB进行，其余

结论

在本文中，我们介绍了隐式稠密草图（IDS），一种快速且具有结构稳定性的随机草图范式。严格的理论分析表明，在提出的IDS框架下，高维向量的?₂范数平方在期望意义上严格保持不变。此外，我们还建立了IDS的全面理论保证，包括非渐近方差界、oblivious 子空间嵌入界、低秩逼近界以及近似的

作者贡献声明

陈柏宇： 写作 – 审阅与编辑，写作 – 原创草稿，可视化，验证，软件，资源，项目管理，方法论，调查，形式分析，数据整理，概念构思。俞文健： 写作 – 审阅与编辑，可视化，指导，软件，资源，项目管理，调查，数据整理。

利益冲突声明

作者声明他们没有已知的竞争性经济利益或个人关系可能会影响本文报告的工作。

陈柏宇|俞文健