Search papers, labs, and topics across Lattice.
This paper introduces a Projected Riemannian Gradient Descent (RGD) algorithm that achieves dimension-independent linear convergence at unit step size for computing the Bures-Wasserstein barycenter of positive definite matrices. By resolving the existing dichotomy between the exponential dependence on dimension in unit-step guarantees and the slow convergence of small-step guarantees, the authors demonstrate a convergence rate of $(1 - \kappa^{-3/2})$, significantly improving upon the best known small-step guarantee. The method leverages a novel Projection Lemma that allows for efficient eigenvalue clipping, ensuring that the computational cost remains unchanged while enhancing convergence properties.
Achieving dimension-independent linear convergence at unit step size could revolutionize how we compute Bures-Wasserstein barycenters in high-dimensional spaces.
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.
