arXiv:2505.12289math.NAcs.DS2025-05被引 4

提出BOLT方法,高效估算大规模矩阵函数的迹,适合内存受限场景。

BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions

  • 基于正交块探针与Lanczos迭代,简化实现且精度媲美最优方法
  • 在近平坦谱情形下优于Hutch++,支持低内存和局部访问限制
  • 适用于计算高维分布间的KL散度与Wasserstein-2距离

高效矩阵迹估计对大规模计算对数行列式、矩阵范数及分布散度至关重要。许多实际应用中,矩阵规模过大无法完整存储或访问,甚至单次矩阵-向量乘法也难以实现,通常仅能获取小块子矩阵或在受限索引集上的局部矩阵-向量乘积。Hutch++虽具最优收敛速度,但依赖随机奇异值分解并假设全矩阵-向量访问,难以在受限环境下应用。本文提出块正交随机Lanczos积分(BOLT),在更简单实现的基础上达到与Hutch++相当的精度,基于随机探测与克里洛夫子空间方法,性能优于Hutch++在近平坦谱情形。为应对内存限制与部分访问约束,引入子块SLQ变体,仅操作小型主子矩阵。该框架可生成代理KL散度估计量,并提供一种高效的高斯分布间Wasserstein-2距离计算方法,均兼容低内存与部分访问场景。理论分析与实验验证表明其在多种高维设置下表现优异。

原文摘要 · Abstract (English)

Efficient matrix trace estimation is essential for scalable computation of log-determinants, matrix norms, and distributional divergences. In many large-scale applications, the matrices involved are too large to store or access in full, making even a single matrix-vector (mat-vec) product infeasible. Instead, one often has access only to small subblocks of the matrix or localized matrix-vector products on restricted index sets. Hutch++ achieves optimal convergence rate but relies on randomized SVD and assumes full mat-vec access, making it difficult to apply in these constrained settings. We propose the Block-Orthonormal Stochastic Lanczos Quadrature (BOLT), which matches Hutch++ accuracy with a simpler implementation based on orthonormal block probes and Lanczos iterations. BOLT builds on the Stochastic Lanczos Quadrature (SLQ) framework, which combines random probing with Krylov subspace methods to efficiently approximate traces of matrix functions, and performs better than Hutch++ in near flat-spectrum regimes. To address memory limitations and partial access constraints, we introduce Subblock SLQ, a variant of BOLT that operates only on small principal submatrices. As a result, this framework yields a proxy KL divergence estimator and an efficient method for computing the Wasserstein-2 distance between Gaussians - both compatible with low-memory and partial-access regimes. We provide theoretical guarantees and demonstrate strong empirical performance across a range of high-dimensional settings.

迹估计随机算法高维统计优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。