euMMD: efficiently computing the MMD two-sample test statistic for univariate data
File(s)s11222-023-10271-x.pdf (662.26 KB)
Published version
Author(s)
Bodenham, Dean A
Kawahara, Yoshinobu
Type
Journal Article
Abstract
The maximum mean discrepancy (MMD) test is a nonparametric kernelised two-sample test that, when using a characteristic kernel, can detect any distributional change between two samples. However, when the total number of d
-dimensional observations is n
, direct computation of the test statistic is O(dn2)
. While approximations with lower computational complexity are known, more efficient methods for computing the exact test statistic are unknown. This paper provides an exact method for computing the MMD test statistic for the univariate case in O(nlogn)
using the Laplacian kernel. Furthermore, this exact method is extended to an approximate method for d
-dimensional real-valued data also with complexity log-linear in the number of observations. Experiments show that this approximate method can have good statistical performance when compared to the exact test, particularly in cases where d>n
.
-dimensional observations is n
, direct computation of the test statistic is O(dn2)
. While approximations with lower computational complexity are known, more efficient methods for computing the exact test statistic are unknown. This paper provides an exact method for computing the MMD test statistic for the univariate case in O(nlogn)
using the Laplacian kernel. Furthermore, this exact method is extended to an approximate method for d
-dimensional real-valued data also with complexity log-linear in the number of observations. Experiments show that this approximate method can have good statistical performance when compared to the exact test, particularly in cases where d>n
.
Date Issued
2023-10
Date Acceptance
2023-06-22
Citation
Statistics and Computing, 2023, 33 (5)
ISSN
0960-3174
Publisher
Springer
Journal / Book Title
Statistics and Computing
Volume
33
Issue
5
Copyright Statement
© The Author(s) 2023. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
License URL
Identifier
http://dx.doi.org/10.1007/s11222-023-10271-x
Publication Status
Published
Article Number
110
Date Publish Online
2023-07-27