On the approximation of the Riemannian barycenter

Simon Mataigne, P.-A. Absil, Nina Miolane · 2025

Read On the approximation of the Riemannian barycenter by Simon Mataigne, P.-A. Absil, Nina Miolane (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15671.txt.

Introduction

Some data live on curved spaces, where even a plain average of points needs new math. Simon Mataigne, P.-A. Absil, and Nina Miolane present a 2025 method for finding such an average, called a barycenter, on a curved space known as a manifold. Exact distance on these spaces is costly to compute, so a fast shortcut has real value.

Their method leans on proven bounds that sit just under and just over the true distance. They test it against a standard step-by-step search that uses exact values, and against a second shortcut based on lifting maps. Trials on the Stiefel manifold, a space of frames used in data work, show how the methods compare. A sound shortcut can speed up tasks from imaging to robot motion.

Catalog record

CREATORSimon Mataigne, P.-A. Absil, Nina Miolane
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15671

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the approximation of the Riemannian barycenter Simon Mataigne, P.-A. Absil, Nina Miolane Abstract We present a method for computing an approximate Riemannian barycenter of a collection of points lying on a Riemannian manifold. Our approach relies on the use of theoretically proven under- and over-approximations of the Riemannian distance function. We compare it to Riemannian steepest descent on the exact objective function of the Riemannian barycenter and to an approach that approximates the Riemannian logarithm using lifting maps. Experiments are conducted on the Stiefel manifold. 1 Introduction Computing the Riemannian barycenter of a dataset lying on a Riemannian manifold is a fundamental problem in statistics on manifolds. See, e.g., [ 14 ] and references therein for applications. We outline the key aspects of this problem. Let \mathcal{M} be a complete manifold equipped with a Riemannian metric g and d_{g}:\mathcal{M}^{2}\rightarrow\mathbb{R} be the distance function induced by the Riemannian metric; see section 2 for details. Given a collection of points \{x_{i}\}_{i=1}^{N}\subset\mathcal{M} and a parameter \nu\geq 1 , let \displaystyle f_{\nu}:\mathcal{M}\rightarrow\mathbb{R}:x\mapsto\left(\sum_{i=1}^{N}d_{g}(x,x_{i})^{\nu}\right)^{\frac{1}{\nu}}\quad\text{and}\quad x^{*}\in\mathrm{arg}\hskip-2.0pt\min_{x\in\mathcal{M}}f_{\nu}(x). (1) Conditions regarding the existence and uniqueness of x^{*} can be found, e.g., in [ 3 ] . The point x^{*} is called a Riemannian l^{\nu} -barycenter of \{x_{i}\}_{i=1}^{N} . Classical choices for \nu are \nu=1,2 , or \nu\rightarrow\infty (minimax problem). For \nu=2 , x^{*} generalizes the notion of Euclidean mean on Riemannian manifolds; it is then often referred to as a Fréchet mean or a Karcher mean [ 11 ] . For \nu=1 , x^{*} generalizes the median. Solving ( 1 ) usually relies on gradient-based optimization algorithms, which require the computation of Riemannian logarithms at each iteration [ 4 ] . However, there are important manifolds lacking tractable algorithms that are guaranteed to compute the Riemannian logarithm within prescribed accuracy, e.g., the Stiefel manifold of orthonormal p -frames in \mathbb{R}^{n} , n>p , defined by \mathrm{St}(n,p)\coloneq\{X\in\mathbb{R}^{n\times p}\ |\ X^{\top}X=I_{p}\}, where I_{p} is the p\times p identity matrix. See [ 1 , 7 , 8 ] and related works for applications of the Stiefel manifold. To tackle this computational bottleneck of ( 1 ), an approach, described in section 4 , approximates the Riemannian logarithm by lifting maps [ 10 , 6 ] . Our approach replaces the exact objective function f_{\nu} in ( 1 ) by an approximate objective function h_{\nu} that is based on theoretically guaranteed under- and over-approximations of f_{\nu} . The estimated Riemannian l^{\nu} -barycenter is then obtained by computing \widehat{x}^{*}\in\mathrm{arg}\hskip-2.0pt\min_{x\in\mathcal{M}}h_{\nu}(x). (2) For h_{\nu} well chosen, \widehat{x}^{*} can be obtained at significantly lower computational cost than x^{*} . A computable bound on \frac{f_{\nu}(\widehat{x}^{*})-f_{\nu}(x^{*})}{f_{\nu}(x^{*})} is given in Theorem 3.1 and numerical comparisons are conducted in section 5 . 2 Preliminaries on manifolds We briefly introduce essential notions of Riemannian geometry. Details can be found, e.g., in [ 1 , 15 ] . A Riemannian metric g , metric for short, is a family \{g_{x}:T_{x}\mathcal{M}\times T_{x}\mathcal{M}\rightarrow\mathbb{R}\}_{x\in\mathcal{M}} of symmetric positive definite bilinear forms that depend smoothly on the location x . For all \xi\in T_{x}\mathcal{M} , the norm induced by the metric is \|\xi\|_{g}\coloneq\sqrt{g_{x}(\xi,\xi)} and the length l_{g}(\gamma) of every continuously differentiable curve \gamma:[0,1]\rightarrow\mathcal{M} is given by l_{g}(\gamma)=\int_{0}^{1}\left\|\frac{\mathrm{d}}{\mathrm{d}t}\gamma(t)\right\|_{g}\mathrm{d}t . If \mathcal{M} is a complete Riemannian manifold, it follows from the Hopf-Rinow theorem [ 15 , Chap. III, Thm. 1.1] that the distance function induced by g satisfies d_{g}(x,\widetilde{x})=\min\{l_{g}(\gamma)\ |\ \gamma:[0,1]\rightarrow\mathcal{M},\gamma(0)=x,\ \gamma(1)=\widetilde{x}\}. A geodesic \gamma_{g}:\mathbb{R}\rightarrow\mathcal{M} is a locally minimizing curve with constant speed v>0 , i.e., for all t\in\mathbb{R} , there is \varepsilon>0 such that for all s\in\mathbb{R} , if |t-s|<\varepsilon , then d_{g}(\gamma_{g}(t),\gamma_{g}(s))=|t-s|v . The Riemannian exponential at x\in\mathcal{M} is the function \mathrm{Exp}_{x}:T_{x}\mathcal{M}\rightarrow\mathcal{M} mapping \xi to the point reached at unit time by the geodesic with starting point x and initial velocity \xi , see, e.g., [ 15 , Chap. II, Sec. 2] . The Riemannian logarithm is defined in [ 12 , 13 ] : Definition 1 Let x,\widetilde{x}\in\mathcal{M} where \mathcal{M} is a complete Riemannian manifold endowed with a metric g . The Riemannian logarithm \mathrm{Log}_{x}(\widetilde{x}) is a set-valued function returning all \xi\in T_{x}\mathcal{M} such that \mathrm{Exp}_{x}(\xi)=\widetilde{x}\text{ and }\|\xi\|_{g}=d_{g}(x,\widetilde{x}). (3) The curves [0,1]\ni t\mapsto\mathrm{Exp}_{x}(t\xi) are then called minimal geodesics. It is known that the subset of \mathcal{M} where \mathrm{Log}_{x} is not a singleton is included in the cut locus \mathcal{C}_{x} and is a zero measure set of \mathcal{M} [ 15 , Chap. III, Lem. 4.4] . In numerical algorithms, it is thus harmless to consider that \mathrm{Log}_{x} returns a singleton. The Riemannian logarithm is key to the Riemannian l^{\nu} -barycenter because, if x\notin\cup_{i=1}^{N}\mathcal{C}_{x_{i}} (and x\notin\{x_{i}\}_{i=1}^{N} if \nu<2 ), then \mathrm{grad}_{x}\left(d_{g}(x,x_{i})^{\nu}\right)=-\nu d_{g}(x,x_{i})^{\nu-2}\mathrm{Log}_{x}(x_{i}) [ 4 , Eq. 2.8] , where \mathrm{grad}_{x} denotes the Riemannian gradient. If \nu\geq 2 and if x^{*}\notin\cup_{i=1}^{N}\mathcal{C}_{x_{i}} , it can be deduced that \mathrm{grad}_{x}(f_{\nu}(x^{*})^{\nu})=0 if and only if [ 4 , Sec. 2.1.5] \sum_{i=1}^{N}d_{g}(x^{*},x_{i})^{\nu-2}\mathrm{Log}_{x^{*}}(x_{i})=0_{x}. (4) The stationarity condition ( 4 ) is illustrated in Figure 1 . Figure 1: An artist view of the Riemannian l^{\nu} -barycenter. The figure represents a collection of points \{x_{i}\}_{i=1}^{3}\subset\mathcal{M} and their Riemannian l^{\nu} -barycenter x^{*} . If \nu\geq 2 , x^{*} must be a first-order stationary point of ( 1 ), i.e., satisfies ( 4 ). 3 Minorizing and majorizing the objective function Assume one knows two functions \widehat{m}_{g},\widehat{M}_{g}:\mathcal{M}^{2}\rightarrow\mathbb{R} such that for all pairs x,\widetilde{x}\in\mathcal{M} , we have \widehat{m}_{g}(x,\widetilde{x})\leq d_{g}(x,\widetilde{x})\leq\widehat{M}_{g}(x,\widetilde{x}). (5) If \mathcal{M} is embedded in the Euclidean space \mathbb{R}^{M} , then \widehat{m}_{g} and \widehat{M}_{g} can often be chosen as functions of the Euclidean distance \|x-\widetilde{x}\|_{\mathrm{E}} . We give explicit examples of such functions on the Stiefel manifold \mathrm{St}(n,p) , n\geq 2p , endowed with the so-called \beta -metric [ 12 , Eq. 2.1] in [ 12 , Thm. 7.1] : \displaystyle\widehat{m}_{\beta}(X,\widetilde{X}) \displaystyle=\min\{1,\sqrt{\beta}\}2\sqrt{p}\arcsin\left(\frac{\|X-\widetilde{X}\|_{\mathrm{E}}}{2\sqrt{p}}\right), \displaystyle\text{and}\quad\widehat{M}_{\beta}(X,\widetilde{X}) \displaystyle=\max\{1,\sqrt{\beta}\}\begin{cases}2\arcsin\left(\frac{\|X-\widetilde{X}\|_{\mathrm{E}}}{2}\right)\text{ if }\|X-\widetilde{X}\|_{\mathrm{E}}\leq 2,\\ \frac{\pi}{2}\|X-\widetilde{X}\|_{\mathrm{E}}\hskip 31.2982pt\ \text{otherwise.}\end{cases} Let us define under- and over-approximations of f_{\nu} from ( 1 ) by \widehat{f}_{\nu}(x)\coloneq\left(\sum_{i=1}^{N}\widehat{m}_{g}(x,x_{i})^{\nu}\right)^{\frac{1}{\nu}}\quad\text{and}\quad\widehat{F}_{\nu}(x)\coloneq\left(\sum_{i=1}^{N}\widehat{M}_{g}(x,x_{i})^{\nu}\right)^{\frac{1}{\nu}}. It is clear by ( 5 ) that for all x\in\mathcal{M} , we have \widehat{f}_{\nu}(x)\leq f_{\nu}(x)\leq\widehat{F}_{\nu}(x) . A choice for h_{\nu} in ( 2 ) that offers theoretical guarantees is the minimization of \widehat{f}_{\nu} . Indeed, by setting h_{\nu}\coloneq\widehat{f}_{\nu} , it follows by the optimality properties of a Riemannian l^{\nu} -barycenter x^{*} and its approximation \widehat{x}^{*}\in\mathrm{arg}\hskip-1.5pt\min_{x\in\mathcal{M}}\widehat{f}_{\nu}(x) that the following sequence of inequalities holds: \widehat{f}_{\nu}(\widehat{x}^{*})\leq\widehat{f}_{\nu}(x^{*})\leq f_{\nu}(x^{*})\leq f_{\nu}(\widehat{x}^{*})\leq\widehat{F}_{\nu}(\widehat{x}^{*}). (6) By ( 6 ), we can bound from above the functional relative error between f_{\nu}(x^{*}) and f_{\nu}(\widehat{x}^{*}) . This is shown in Theorem 3.1 . Theorem 3.1 Let \{x_{i}\}_{i=1}^{N}\subset\mathcal{M} , f_{\nu} and x^{*} be defined as in ( 1 ). Moreover, let \widehat{x}^{*}\in\mathrm{arg}\hskip-1.5pt\min_{x\in\mathcal{M}}\widehat{f}_{\nu}(x) , then \frac{f_{\nu}(\widehat{x}^{*})-f_{\nu}(x^{*})}{f_{\nu}(x^{*})}\leq\frac{\widehat{F}_{\nu}(\widehat{x}^{*})-\widehat{f}_{\nu}(\widehat{x}^{*})}{\widehat{f}_{\nu}(\widehat{x}^{*})}. (7) Proof By ( 6 ), we have f_{\nu}(\widehat{x}^{*})-f_{\nu}(x^{*})\leq\widehat{F}_{\nu}(\widehat{x}^{*})-\widehat{f}_{\nu}(\widehat{x}^{*}) . Moreover, it also holds that \widehat{f}_{\nu}(\widehat{x}^{*})\leq f_{\nu}(x^{*}) . This concludes the proof. The upper bound from Theorem 3.1 only depends on \widehat{f}_{\nu},\widehat{F}_{\nu} and \widehat{x}^{*} , which can all be computed at low computational cost. Moreover, the upper bound ( 7 ) can be small in practice, as exemplified in section 5 . For any function h_{\nu} in ( 2 ), the distance d_{g}(x^{*},\widehat{x}^{*}) between a barycenter x^{*} and its approximation \widehat{x}^{*} can be bounded from above by the computable quantity N^{-\frac{1}{\nu}}2\widehat{F}_{\nu}(\widehat{x}^{*}) , as shown in Theorem 3.2 . Theorem 3.2 Let \{x_{i}\}_{i=1}^{N}\subset\mathcal{M} , f_{\nu} and x^{*} be defined as in ( 1 ). Then, for all x\in\mathcal{M} , we have d_{g}(x^{*},x)\leq N^{-\frac{1}{\nu}}2f_{\nu}(x)\leq N^{-\frac{1}{\nu}}2\widehat{F}_{\nu}(x) . Proof By the triangle inequality, for i=1,...,N

Read the complete text