技术摘要：利用快速草图加速幂法以实现更强的低秩近似

问题陈述

计算大型矩阵 $A \in \mathbb{R}^{m \times n}$ 的前几个奇异值及其对应的奇异向量是数据科学中的一项基本任务。幂法（及其块变体）是提取这些分量以构建低秩近似的一种标准方法。然而，当目标秩 $k$ 较大时，幂法所需的重复矩阵乘法（具体为计算 $(AA^\top)^q A \Omega$）会成为计算瓶颈。

虽然快速草图（使用结构化随机矩阵 $S$ 计算草图 $\tilde{A} = AS$）是避免降维中昂贵矩阵乘法的有力工具，但将其与幂法简单结合会带来挑战：

1. 将 $A$ 重复应用于草图 $(AA^\top)^q AS$ 会抵消草图带来的速度优势。
2. 在幂迭代中完全用草图 $\tilde{A}$ 替代 $A$（即计算 $(\tilde{A}\tilde{A}^\top)^q \tilde{A}\Omega$）此前在理论上尚未得到充分理解。尚不清楚这种“草图幂法”是否能提供强有力的近似保证，因为草图 $\tilde{A}$ 是 $A$ 的“粗糙”版本，且即使迭代次数 $q \to \infty$，该方法也无法收敛到 $A$ 的精确前 $k$ 维子空间。

方法论

作者提出了一种将快速草图直接集成到幂法迭代中的框架。与其使用经典的范围查找器 $Q = \text{orth}((AA^\top)^q A \Omega)$，他们计算：
$$Q = \text{orth}\left( (\tilde{A}\tilde{A}^\top)^q \tilde{A} \Omega \right)$$
其中 $\tilde{A} = AS$ 是大小为 $m \times l$ 的草图（满足 $l \gg k$ 但 $l \ll n$），$\Omega$ 是大小为 $l \times k$ 的高斯矩阵。

理论创新：正则化谱近似

核心理论贡献在于利用正则化谱近似来分析该方法。与依赖高斯矩阵旋转不变性或子空间嵌入性质的传统分析不同，该方法利用以下性质：对于适当选择的正则化参数 $\lambda$ 和精度 $\epsilon$：
$$(1-\epsilon)(AA^\top + \lambda I) \preceq \tilde{A}\tilde{A}^\top + \lambda I \preceq (1+\epsilon)(AA^\top + \lambda I)$$
作者证明了：

1. 利用该性质可以恢复经典范围查找器的保证。
2. 关于草图 $\tilde{A}$ 的子空间近似保证可以转化为关于原始矩阵 $A$ 的保证，其误差项为依赖于正则化谱近似质量的加性误差项。
3. 即使初始化涉及结构化草图矩阵与稠密高斯矩阵的混合，该分析依然成立。

主要贡献

本文针对三种具体应用开发了算法及理论保证：

1. 草图驱动的范围查找器

作者为使用草图幂法构建范围查找器 $Q$ 提供了理论保证。

• 结果：对于稀疏草图尺寸 $l \gg k$，该方法实现的近似误差 $\|A - QQ^\top A\|_2$ 被 $(1+\epsilon)\sigma_{k+1}^2(A) + \epsilon \sum_{i>l} \sigma_i^2(A)$ 所界定。
• 意义：这允许进行一种权衡，即较大的草图尺寸 $l$ 可减小加性误差项，从而在保持较低单次迭代成本的同时，相比经典方法用更少的迭代次数 $q$ 实现强近似。

2. 草图驱动的低秩分解

标准随机 SVD 需要昂贵的最终矩阵乘积 $B = Q^\top A$。作者将草图幂法集成到广义 Nyström框架中，以规避此瓶颈。

• 算法：使用第二个草图矩阵 $S_2$ 来近似 $A$ 在由 $Q$ 定义的子空间上的投影，而无需显式计算 $Q^\top A$。
• 结果：对于 $n \times n$ 矩阵且 $k \le O(\sqrt{n})$，该算法在 $\tilde{O}(n^2)$ 时间内计算出一个秩为 $O(k)$ 的分解 $\hat{A} = YX$，其误差保证为 $\|A - YX\|_2 \le \sqrt{k+1} \cdot \sigma_{k+1}(A)$。
• 对比：若无草图幂法，在相同时间预算下实现类似的误差界是不可能的；现有方法要么误差保证较弱（$O(\sqrt{n/k})$），要么时间复杂度更高（$\tilde{O}(n^2 k)$）。

3. 草图驱动的 Nyström 近似

对于对称半正定（PSD）矩阵，作者针对Nyström 近似优化了该方法。

• 算法：通过在缩减矩阵 $\tilde{W} = S^\top AS$（大小为 $l \times l$）而非完整矩阵或单一草图上进行幂迭代，将草图幂法集成到经典 Nyström 过程中。
• 结果：这产生了一个具有与一般情况相似误差界的 PSD 分解，具体为 $\|A - CW^\dagger C^\top\| \le (1+\epsilon)\lambda_{k+1}(A) + \epsilon \sum_{i>l} \lambda_i(A)$。

实验结果

作者在三个大型数据集上验证了其理论：smallnorb（$24300 \times 9216$）、ImageNet（$20800 \times 50176$）以及合成polydecay矩阵（$30000 \times 15000$）。

• 性能：草图驱动的随机 SVD 达到中等较小相对误差（例如 0.1）的速度显著快于经典随机 SVD。
• 权衡：虽然误差最终会趋于平稳（由于草图带来的加性误差项），但该方法比经典方法更早达到这一平稳点，从而弥补了构建初始草图的开销。
• 分解：与无草图的基线方法相比，草图驱动的低秩分解（算法 2）也观察到了类似的计算改进。

意义与主张

本文声称提供了一种简单且可证明高效的框架，用于加速幂法。

• 理论新颖性：主要贡献在于从传统分析（高斯不变性/子空间嵌入）转向正则化谱近似。这使得作者能够在不依赖草图矩阵为高斯分布的情况下分析草图幂法，从而释放快速结构化草图（如 CountSketch）的计算优势。
• 实际影响：该框架提供了一种途径，可在降低计算复杂度的同时，在基准问题上获得强大的数值性能，特别是针对那些因矩阵乘法而受限的大目标秩场景。
• 谦逊声明：作者承认，随着 $q \to \infty$，该方法无法像经典方法那样收敛到与前 $k$ 维子空间的完美对齐，但他们认为，由于降低了单次迭代成本，该方法能“更快地达到足够好的近似”。他们将此定位为针对计算受限环境的解决方案，在这些环境中，即使经典方法的单次迭代成本也是难以承受的。