arXiv:2609.03762cs.LGmath.OC2026-09

提出新算法实现矩阵巴氏中心快速收敛,无需调参且不依赖维度。

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

  • 设计投影梯度法,在单位步长下保持稳定迭代。
  • 收敛速度与维度无关,条件数越小越快,理论优于旧方法。
  • 算法开销几乎为零,适合大规模矩阵计算场景。

正定矩阵的Bures-Wasserstein(BW)巴氏中心计算在机器学习、最优传输和量子信息中广泛应用。实践中常用的单位步长黎曼梯度下降(RGD)收敛迅速,但现有分析存在两难:单位步长保证需指数依赖维度,而维度无关保证则要求极小步长,牺牲了实际速度。本文通过提出投影式RGD算法,首次在单位步长下实现维度无关的线性收敛。收敛速率$(1 - \kappa^{-3/2})$,其中$\kappa$为矩阵集的条件数,相比最优小步长方案($\kappa^{3/2}$ vs $\kappa^{5/2}$迭代复杂度)有显著提升。核心是提出一个新颖的投影引理:将正定矩阵特征值截断至区间$[\alpha, \beta]$,即为在集合\{S : \alpha I \leq S \leq \beta I\}上的闭式、非扩张(1-Lipschitz)BW投影——这一结论无法由凸性推导。该投影无需额外计算成本,可复用下一迭代必做的特征分解,因此每步开销不变。该分析亦适用于Brahmachari等(2025)的不变矩阵投影问题,其固定点算法被识别为在全测地子流形上的单位步长RGD,从而直接扩展维度无关保证。

原文摘要 · Abstract (English)

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, $(1 - \kappa^{-3/2})$, where $\kappa$ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee ($\kappa^{3/2}$ versus $\kappa^{5/2}$ iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval $[\alpha, \beta]$ is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set $\{S : \alpha I \leq S \leq \beta I\}$ -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

最优传输矩阵优化黎曼几何收敛分析

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