Wolfowitz’s theorem and consensus algorithms in Hadamard spaces
HTML articles powered by AMS MathViewer
- by P. Grohs PDF
- Proc. Amer. Math. Soc. 143 (2015), 4403-4414 Request permission
Abstract:
We provide a generalization of Wolfowitz’s theorem on the products of stochastic, indecomposable and aperiodic (SIA) matrices to metric spaces with nonpositive curvature. As a result we show convergence for a wide class of distributed consensus algorithms operating on these spaces.References
- A. D. Aleksandrov, A theorem on triangles in a metric space and some of its applications, Trudy Mat. Inst. Steklov. 38 (1951), 5–23 (Russian). MR 0049584
- A. Aleksandrov, Über eine Verallgemeinerung der Riemannschen Geometrie, Schriftenreihe des Forschungsinstituts für Mathematik bei der Deutschen Akademie der Wissenschaften zu Berlin, 1:33–84, 1957.
- Federico Ardila, Megan Owen, and Seth Sullivant, Geodesics in $\rm CAT(0)$ cubical complexes, Adv. in Appl. Math. 48 (2012), no. 1, 142–163. MR 2845512, DOI 10.1016/j.aam.2011.06.004
- Werner Ballmann, Lectures on spaces of nonpositive curvature, DMV Seminar, vol. 25, Birkhäuser Verlag, Basel, 1995. With an appendix by Misha Brin. MR 1377265, DOI 10.1007/978-3-0348-9240-7
- Louis J. Billera, Susan P. Holmes, and Karen Vogtmann, Geometry of the space of phylogenetic trees, Adv. in Appl. Math. 27 (2001), no. 4, 733–767. MR 1867931, DOI 10.1006/aama.2001.0759
- Victor Chepoi, Graphs of some $\textrm {CAT}(0)$ complexes, Adv. in Appl. Math. 24 (2000), no. 2, 125–179. MR 1748966, DOI 10.1006/aama.1999.0677
- Albert Cohen and Nira Dyn, Nonstationary subdivision schemes and multiresolution analysis, SIAM J. Math. Anal. 27 (1996), no. 6, 1745–1769. MR 1416517, DOI 10.1137/S003614109427429X
- Jonathan Dahl, Steiner problems in optimal transport, Trans. Amer. Math. Soc. 363 (2011), no. 4, 1805–1819. MR 2746666, DOI 10.1090/S0002-9947-2010-05065-2
- O. Ebner, Nonlinear Markov semigroups and refinement schemes on metric spaces, Arxiv preprint arXiv:1112.6003, 2011.
- Oliver Ebner, Convergence of refinement schemes on metric spaces, Proc. Amer. Math. Soc. 141 (2013), no. 2, 677–686. MR 2996972, DOI 10.1090/S0002-9939-2012-11331-0
- A. Feragen, S. Hauberg, M. Nielsen, and F. Lauze, Means in spaces of tree-like shapes, Submitted to ICCV, 2011.
- Philipp Grohs, A general proximity analysis of nonlinear subdivision schemes, SIAM J. Math. Anal. 42 (2010), no. 2, 729–750. MR 2607928, DOI 10.1137/09075963X
- Ali Jadbabaie, Jie Lin, and A. Stephen Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. Automat. Control 48 (2003), no. 6, 988–1001. MR 1986266, DOI 10.1109/TAC.2003.812781
- H. Karcher, Mollifier smoothing and Riemannian center of mass, Communications on Pure and Applied Mathematics, 30:509–541, 1977.
- Serge Lang, Fundamentals of differential geometry, Graduate Texts in Mathematics, vol. 191, Springer-Verlag, New York, 1999. MR 1666820, DOI 10.1007/978-1-4612-0541-8
- M. Owen and J. Provan, A fast algorithm for computing geodesic distances in tree space, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 8(1):2–13, 2011.
- X. Pennec, P. Fillard, and N. Ayache, A Riemannian framework for tensor computing, International Journal of Computer Vision, 66(1):41–66, 2006.
- R. Sepulchre, Consensus on nonlinear spaces, Annual Reviews in Control, 35:56–64, 2011.
- Karl-Theodor Sturm, Nonlinear martingale theory for processes with values in metric spaces of nonpositive curvature, Ann. Probab. 30 (2002), no. 3, 1195–1222. MR 1920105, DOI 10.1214/aop/1029867125
- Karl-Theodor Sturm, Probability measures on metric spaces of nonpositive curvature, Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002) Contemp. Math., vol. 338, Amer. Math. Soc., Providence, RI, 2003, pp. 357–390. MR 2039961, DOI 10.1090/conm/338/06080
- John N. Tsitsiklis, Dimitri P. Bertsekas, and Michael Athans, Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Automat. Control 31 (1986), no. 9, 803–812. MR 853431, DOI 10.1109/TAC.1986.1104412
- Johannes Wallner and Nira Dyn, Convergence and $C^1$ analysis of subdivision schemes on manifolds by proximity, Comput. Aided Geom. Design 22 (2005), no. 7, 593–622. MR 2169051, DOI 10.1016/j.cagd.2005.06.003
- J. Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices, Proc. Amer. Math. Soc. 14 (1963), 733–737. MR 154756, DOI 10.1090/S0002-9939-1963-0154756-3
- Gang Xie and Thomas P.-Y. Yu, Smoothness equivalence properties of general manifold-valued data subdivision schemes, Multiscale Model. Simul. 7 (2008), no. 3, 1073–1100. MR 2480112, DOI 10.1137/080718723
Additional Information
- P. Grohs
- Affiliation: Swiss Federal Institute of Technology - Zurich, Department of Mathematics, Raem- istrasse 101, 8092 Zurich, Switzerland
- Received by editor(s): August 25, 2012
- Received by editor(s) in revised form: March 20, 2014
- Published electronically: June 16, 2015
- Additional Notes: The research of the author was partly supported by the European Research Council under grant ERC AdG 247277, as well as by the Swiss National Fund under grant SNF 200021_140635
- Communicated by: Walter Van Assche
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 4403-4414
- MSC (2010): Primary 53C23, 60J20, 65P99
- DOI: https://doi.org/10.1090/proc/12513
- MathSciNet review: 3373939