Means in complete manifolds: uniqueness and approximation

Arnaudon, Marc; Miclo, Laurent

ESAIM: Probability and Statistics, Tome 18 (2014), pp. 185-206.

Let M be a complete Riemannian manifold, M ∈ ℕ and p ≥ 1. We prove that almost everywhere on x = (x₁,...,x_N) ∈ M^N for Lebesgue measure in M^N, the measure $d\mu \left(x\right)=\frac{1}{N}{\sum }_{k=1}^N{\delta }_{x_k}$ has a unique p-mean e_p(x). As a consequence, if X = (X₁,...,X_N) is a M^N-valued random variable with absolutely continuous law, then almost surely μ(X(ω)) has a unique p-mean. In particular if (X_n)_n ≥ 1 is an independent sample of an absolutely continuous law in M, then the process e_p,n(ω) = e_p(X₁(ω),...,X_n(ω)) is well-defined. Assume M is compact and consider a probability measure ν in M. Using partial simulated annealing, we define a continuous semimartingale which converges in probability to the set of minimizers of the integral of distance at power p with respect to ν. When the set is a singleton, it converges to the p-mean.

[1] B. Afsari, Riemannian Lp center of mass: existence, uniqueness, and convexity. Proc. Amer. Math. Soc. S 0002-9939 (2010) 10541-5. (electronic) | MR | Zbl

[2] B. Afsari, R. Tron and R. Vidal, On the convergence of gradient descent for finding the Riemannian center of mass. arXiv:1201.0925. | MR | Zbl

[3] M. Arnaudon and F. Nielsen, Medians and means in Finsler geometry. LMS J. Comput. Math. 15 (2012) 23-37. | MR | Zbl

[4] M. Arnaudon, C. Dombry, A. Phan and L. Yang, Stochastic algorithms for computing means of probability measures Stoch. Proc. Appl. 122 (2012) 1437-1455. | MR | Zbl

[5] M. Arnaudon and F. Nielsen, On computing the Riemannian 1-Center. Comput. Geom. 46 (2013) 93-104. | MR | Zbl

[6] M. Bădoiu and K.L. Clarkson, Smaller core-sets for balls, Proc. of the fourteenth Annual ACM-SIAM Symposium on Discrete algorithms. Soc. Industrial Appl. Math. Philadelphia, PA, USA (2003) 801-802. | MR | Zbl

[7] R. Bhattacharya and V. Patrangenaru, Large sample theory of intrinsic and extrinsic sample means on manifolds (i). Ann. Statis. 31 (2003) 1-29. | MR | Zbl

[8] S. Bonnabel, Convergence des méthodes de gradient stochastique sur les variétés riemanniennes. In GRETSI, Bordeaux (2011).

[9] H. Cardot, P. Cénac and P.-A. Zitt, Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm, Bernoulli. | Zbl

[10] B. Charlier, Necessary and sufficient condition for the existence of a Fréchet mean on the circle. arXiv:1109.1986. | Numdam | MR

[11] P.T. Fletcher, S. Venkatasubramanian and S. Joshi, The geometric median on Riemannian manifolds with application to robust atlas estimation. NeuroImage 45 (2009) S143-S152.

[12] D. Groisser, Newton's method, zeroes of vector fields, and the Riemannian center of mass. Adv. Appl. Math. 33 (2004) 95-135. | MR | Zbl

[13] D. Groisser, On the convergence of some Procrustean averaging algorithms. Stochastics 77 (2005) 31-60. | MR | Zbl

[14] E.P. Hsu, Estimates of derivatives of the heat kernel on a compact Riemannian manifold. Proc. Amer. Math. Soc. 127 (1999) 3739-3744. | MR | Zbl

[15] R. Holley, S. Kusuoka and D. Stroock, Asymptotics of the spectral gap with applications to the theory of simulated annealing. J. Funct. Anal. 83 (1989) 333-347. | MR | Zbl

[16] R. Holley and D. Stroock, Annealing via Sobolev inequalities. Commun. Math. Phys. 115 (1988) 553-569. | MR | Zbl

[17] T. Hotz and S. Huckemann, Intrinsic mean on the circle: Uniqueness, Locus and Asymptotics. arXiv:org1108:2141. | MR

[18] W.S. Kendall, Probability, convexity and harmonic maps with small image I: uniqueness and fine existence. Proc. London Math. Soc. 61 (1990) 371-406. | MR | Zbl

[19] H. Le, Estimation of Riemannian barycentres. LMS J. Comput. Math. 7 (2004) 193-200. | MR | Zbl

[20] L. Miclo, Recuit simulé sans potentiel sur une variété compacte. Stoch. and Stochastic Reports 41 (1992) 23-56. | MR | Zbl

[21] L. Miclo, Recuit simulé partiel, Stoch. Process. Appl. 65 (1996) 281-298. | MR | Zbl

[22] S.J. Sheu, Some estimates of the transition density function of a nondegenerate diffusion Markov process. Ann. Probab. 19 (1991) 538-561. | MR | Zbl

[23] K.T. Sturm, Probability measures on metric spaces of nonpositive curvature, Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002). Contemp. Math. Amer. Math. Soc. 338 (2003) 357-390. | MR | Zbl

[24] E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math. J. 43 (1937) 355-386. | Zbl

[25] L. Yang, Riemannian median and its estimation. LMS J. Comput. Math. 13 (2010) 461-479. | MR | Zbl

[26] L. Yang, Some properties of Frechet medians in Riemannian manifolds. Preprint.