Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs

DOI10.1214/19-AOS1913MaRDI QIDQ2215763zbMATH OpenOpenAlexFDO

Authors Bhaswar B. Bhattacharya

Publication date 14 December 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.00384, https://projecteuclid.org/euclid.aos/1600480935

zbMATH Keywords

geometric graphmultivariate distributionsnearest-neighbor graphsnonparametric hypothesis testing

Mathematics Subject Classification ID

Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05) Central limit and other weak theorems (60F05) Characterization and structure theory of statistical distributions (62E10) Asymptotic distribution theory in statistics (62E20) Nonparametric hypothesis testing (62G10) Hypothesis testing in multivariate analysis (62H15)

Abstract: In this paper, we consider the problem of testing the equality of two multivariate distributions based on geometric graphs constructed using the interpoint distances between the observations. These include the tests based on the minimum spanning tree and the $K$-nearest neighbor (NN) graphs, among others. These tests are asymptotically distribution-free, universally consistent and computationally efficient, making them particularly useful in modern applications. However, very little is known about the power properties of these tests. In this paper, using the theory of stabilizing geometric graphs, we derive the asymptotic distribution of these tests under general alternatives, in the Poissonized setting. Using this, the detection threshold and the limiting local power of the test based on the $K$-NN graph are obtained, where interesting exponents depending on dimension emerge. This provides a way to compare and justify the performance of these tests in different examples.

Review text

This work deals with the problem of testing the equality of two multivariate distributions based on geometric graphs constructed using the interpoint distances between the observations. In addition, the author uses the tests based on minimum spanning tree and \(K\)-nearest neighbor (NN) graphs. However, there is little work on the power properties of these tests. Moreover, the theory of stabilizing geometric graphs was used from which the author derives the asymptotic distribution of these tests under general alternatives, in the Fish-filled frame. Thanks to this, the detection threshold and the local limit power of the test based on the \(K\)-NN graph are obtained, where interesting exponents according to the dimension emerge. This makes it possible to compare and justify the performance of these tests in different examples.

Recommendations

• A General Asymptotic Framework for Distribution-Free Graph-Based Two-Sample Tests
• Graph-theoretic multisample tests of equality in distribution for high dimensional data
• A new multivariat two-sample test using regular minimum-weight spanning subgraphs
• A weighted edge-count two-sample test for multivariate and object data
• On some graph-based two-sample tests for high dimension, low sample size data

Cites work

• A Distribution Free Version of the Smirnov Two Sample Test in the p-Variate Case
• A distribution-free two-sample run test applicable to high-dimensional data
• A General Asymptotic Framework for Distribution-Free Graph-Based Two-Sample Tests
• A kernel two-sample test
• A multivariate two-sample test based on the number of nearest neighbor type coincidences
• A Quality Index Based on Data Depth and Multivariate Rank Tests
• An Exact Distribution-Free Test Comparing Two Multivariate Distributions based on Adjacency
• Asymptotics for Euclidean minimal spanning trees on random points
• Gaussian limits for random geometric measures
• scientific article; zbMATH DE number 3541764 (Why is no real title available?)
• scientific article; zbMATH DE number 3563978 (Why is no real title available?)
• scientific article; zbMATH DE number 3037724 (Why is no real title available?)
• Limit theorems in discrete stochastic geometry
• Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests
• Multivariate goodness-of-fit on flat and curved spaces via nearest neighbor distances
• Multivariate Two-Sample Tests Based on Nearest Neighbors
• New test for the multivariate two-sample problem based on the concept of minimum energy
• On a new multivariate two-sample test.
• On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other
• On distribution-free tests for the multivariate two-sample location-scale model
• On the consistency of the crossmatch test
• On the multivariate runs test
• Optimal algorithms for testing closeness of discrete distributions
• Permutation tests for equality of distributions in high-dimensional settings
• Random Geometric Graphs
• Reducing multidimensional two-sample data to one-dimensional interpoint comparisons
• Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test
• Testing closeness of discrete distributions
• Two-Sample Tests for Multivariate Distributions
• Weak laws of large numbers in geometric probability

Cited in

(14)

• Testing uniformity on high-dimensional spheres: the non-null behaviour of the Bingham test
• Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing
• Classification accuracy as a proxy for two-sample testing
• A weighted edge-count two-sample test for multivariate and object data
• scientific article; zbMATH DE number 2163513 (Why is no real title available?)
• A General Asymptotic Framework for Distribution-Free Graph-Based Two-Sample Tests
• Distribution-Free Multisample Tests Based on Optimal Matchings With Applications to Single Cell Genomics
• Kernel two-sample tests for manifold data
• A Kernel Measure of Dissimilarity between M Distributions
• Two-sample distribution tests in high dimensions via max-sliced Wasserstein distance and bootstrapping
• Methods for quantifying dataset similarity: a review, taxonomy and comparison
• Adaptive block-based change-point detection for sparse spatially clustered data with applications in remote sensing imaging
• On a Class of Sobolev Tests for Symmetry, their Detection Thresholds, and Asymptotic Powers
• A fully distribution-free and consistent two-sample test based on projection averaging

This page was built for publication: Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2215763)