Metrics and barycenters for point pattern data. (English) Zbl 1447.62140

Summary: We introduce the transport-transform and the relative transport-transform metrics between finite point patterns on a general space, which provide a unified framework for earlier point pattern metrics, in particular the generalized spike time and the normalized and unnormalized optimal subpattern assignment metrics. Our main focus is on barycenters, i.e., minimizers of a \(q\)-th-order Fréchet functional with respect to these metrics. We present a heuristic algorithm that terminates in a local minimum and is shown to be fast and reliable in a simulation study. The algorithm serves as a general plug-in method that can be applied to point patterns on any state space where an appropriate algorithm for solving the location problem for individual points is available. We present applications to geocoded data of crimes in Euclidean space and on a street network, illustrating that barycenters serve as informative summary statistics. Our work is a first step toward statistical inference in covariate-based models of repeated point pattern observations.


62R20 Statistics on metric spaces
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
62P25 Applications of statistics to social sciences


ttbary; R
Full Text: DOI arXiv


[1] Agueh, M.; Carlier, G., Barycenters in the Wasserstein space, SIAM J. Math. Anal., 43, 904-924 (2011) · Zbl 1223.49045
[2] Anderes, E.; Borgwardt, S.; Miller, J., Discrete Wasserstein barycenters: optimal transport for discrete data, Math. Methods Oper. Res., 84, 2, 389-409 (2016) · Zbl 1353.90074
[3] Baddeley, A.; Rubak, E.; Turner, R., Spatial Point Patterns: Methodology and Applications with R (2015), Boca Raton: Chapman and Hall/CRC, Boca Raton
[4] Bandelt, H-J; Crama, Y.; Spieksma, FCR, Approximation algorithms for multi-dimensional assignment problems with decomposable costs, Discrete Appl. Math., 49, 25-50 (1994) · Zbl 0799.90077
[5] Bertsekas, DP, The auction algorithm: a distributed relaxation method for the assignment problem, Ann. Oper. Res., 14, 105-123 (1988) · Zbl 0788.90055
[6] Błaszczyszyn, B.; Haenggi, M.; Keeler, P.; Mukherjee, S., Stochastic Geometry Analysis of Cellular Networks (2018), Cambridge: Cambridge University Press, Cambridge · Zbl 1393.60003
[7] Borgwardt, S.: An LP-based, strongly polynomial 2-approximation algorithm for sparse Wasserstein barycenters. Preprint (2019). arXiv:1704.05491v5
[8] Borgwardt, S., Patterson, S.: Improved linear programs for discrete barycenters. INFORMS J Optim (2018). arXiv:1803.11313
[9] Chiaraviglio, L.; Cuomo, F.; Maisto, M.; Gigli, A.; Lorincz, J.; Zhou, Y.; Zhao, Z.; Qi, C.; Zhang, H., What is the best spatial distribution to model base station density? A deep dive into two European mobile networks, IEEE Access, 4, 1434-1443 (2016)
[10] Chizat, L.: Unbalanced Optimal Transport: Models, Numerical Methods, Applications. Ph.D. thesis, PSL Research University (2017)
[11] Chizat, L.; Peyré, G.; Schmitzer, B.; Vialard, F-X, Scaling algorithms for unbalanced optimal transport problems, Math. Comput., 87, 314, 2563-2609 (2018) · Zbl 1402.90120
[12] Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C., Introduction to Algorithms (2009), Cambridge: MIT Press, Cambridge
[13] Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. In: Xing, E.P., Jebara, T. (eds.) Proceedings of the 31st International Conference on Machine Learning, pp. 685-693 (2014)
[14] del Barrio, E.; Cuesta-Albertos, JA; Matrán, C.; Mayo-Íscar, A., Robust clustering tools based on optimal transportation, Stat. Comput., 29, 139-160 (2019) · Zbl 1430.62130
[15] Diez, DM; Schoenberg, FP; Woody, CD, Algorithms for computing spike time distance and point process prototypes with application to feline neuronal responses to acoustic stimuli, J. Neurosci. Methods, 203, 1, 186-192 (2012)
[16] Diggle, PJ, Statistical Analysis of Spatial and Spatio-Temporal Point Patterns (2013), Boca Raton: Chapman and Hall/CRC, Boca Raton
[17] Dubey, P., Müller, H.-G.: Fréchet analysis of variance for random objects. Preprint 106(4), 803-821 (2019a) · Zbl 1435.62383
[18] Dubey, P., Müller, H.-G.: Functional models for time-varying random objects. Preprint (2019b). arXiv:1907.10829
[19] Fréchet, M., Les éléments aléatoires de nature quelconque dans un espace distancié, Ann. Inst. H. Poincaré, 10, 215-310 (1948) · Zbl 0035.20802
[20] Hakimi, SL, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res., 12, 3, 456-458 (1964) · Zbl 0123.00305
[21] Koliander, G.; Schuhmacher, D.; Hlawatsch, F., Rate-distortion theory of finite point processes, IEEE Trans. Inf. Theory, 64, 8, 5832-5861 (2018) · Zbl 1401.60091
[22] Konstantinoudis, G., Schuhmacher, D., Ammann, R., Diesch, T., Kuehni, C., Spycher, B.D.: Bayesian spatial modelling of childhood cancer incidence in Switzerland using exact point data: a nationwide study during 1985-2015. Preprint (2019). https://www.medrxiv.org/content/early/2019/07/15/19001545
[23] Kuhn, HW, The Hungarian method for the assignment problem, Naval Res. Logist. Quart., 2, 83-97 (1955)
[24] Liero, M.; Mielke, A.; Savaré, G., Optimal entropy-transport problems and a new Hellinger-Kantorovich distance between positive measures, Invent. Math., 211, 3, 969-1117 (2018) · Zbl 1412.49089
[25] Lin, Z., Müller, H.-G.: Total variation regularized Fréchet regression for metric-space valued data. Preprint (2019). arXiv:1904.09647
[26] Lombardo, L.; Opitz, T.; Huser, R., Point process-based modeling of multiple debris flow landslides using INLA: an application to the 2009 Messina disaster, Stoch. Environ. Res Risk Assess., 32, 7, 2179-2198 (2018)
[27] Luenberger, DG; Ye, Y., Linear and Nonlinear Programming (2008), New York: Springer, New York
[28] Mateu, J.; Schoenberg, FP; Diez, DM; Gonzáles, JA; Lu, W., On measures of dissimilarity between point patterns: classification based on prototypes and multidimensional scaling, Biom. J., 57, 2, 340-358 (2015) · Zbl 1310.62117
[29] Moradi, M., Mateu, J.: First and second-order characteristics of spatio-temporal point processes on linear networks. J. Comput. Graph. Stat. (2019, to appear)
[30] Moradi, M.; Rodriguez-Cortes, F.; Mateu, J., On kernel-based intensity estimation of spatial point patterns on linear networks, J. Comput. Graph. Stat., 27, 2, 302-311 (2018)
[31] Müller, R., Schuhmacher, D.: ttbary: barycenter methods for spatial point patterns. R package version 0.1-1. (2019) https://cran.r-project.org/package=ttbary
[32] Petersen, A.; Müller, H-G, Fréchet regression for random objects with Euclidean predictors, Ann. Stat., 47, 2, 691-719 (2019) · Zbl 1417.62091
[33] Peyré, G.; Cuturi, M., Computational optimal transport Foundations and Trends®, Mach. Learn., 11, 5-6, 355-607 (2019)
[34] R Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2019)
[35] Rakshit, S., Davies, T., Moradi, M., McSwiggan, G., Nair, G., Mateu, J., Baddeley, A.: Fast kernel smoothing of point patterns on a large network using 2d convolution. Int. Stat. Rev. (2019)
[36] Samartsidis, P.; Eickhoff, CR; Eickhoff, SB; Wager, TD; Barrett, LF; Atzil, S.; Johnson, TD; Nichols, TE, Bayesian log-Gaussian Cox process regression: applications to meta-analysis of neuroimaging working memory studies, J. R. Stat. Soc. Ser. C, 68, 1, 217-234 (2019)
[37] Schmitz, MA; Heitz, M.; Bonneel, N.; Ngole, F.; Coeurjolly, D.; Cuturi, M.; Peyré, G.; Starck, J-L, Wasserstein dictionary learning: optimal transport-based unsupervised nonlinear dictionary learning, SIAM J. Imaging Sci., 11, 1, 643-678 (2018) · Zbl 1437.94027
[38] Schoenberg, FP; Tranbarger, KE, Description of earthquake aftershock sequences using prototype point patterns, Environmetrics, 19, 3, 271-286 (2008)
[39] Schuhmacher, D.: Stein’s method for approximating complex distributions, with a view towards point processes. In: Schmidt, V. (ed.) Stochastic Geometry, Spatial Statistics and Random Fields, Vol. II: Models and Algorithms. Lecture Notes in Mathematics, vol. 2120, pp. 1-30. Springer (2014) · Zbl 1369.62036
[40] Schuhmacher, D.; Vo, B-T; Vo, B-N, A consistent metric for performance evaluation of multi-object filters, IEEE Trans. Signal Process., 56, 8-1, 3447-3457 (2008) · Zbl 1390.94399
[41] Schuhmacher, D.; Xia, A., A new metric between distributions of point processes, Adv. Appl. Probab., 40, 3, 651-672 (2008) · Zbl 1155.60020
[42] Victor, JD; Purpura, KP, Metric-space analysis of spike trains: theory, algorithms and application, Netw. Comput Neural Syst., 8, 127-164 (1997) · Zbl 0927.92011
[43] Weiszfeld, E., Sur le point pour lequel la somme des distances de \(n\) points donnés est minimum, Tohoku Math. J., 43, 355-386 (1937) · Zbl 0017.18007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.