On combinatorial testing problems

Abstract

We study a class of hypothesis testing problems in which, upon observing the realization of an $n$-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal distribution or, alternatively, whether there is a subset of the components belonging to a certain given class of sets whose elements have been ``contaminated,'' that is, have a mean different from zero. We establish some general conditions under which testing is possible and others under which testing is hopeless with a small risk. The combinatorial and geometric structure of the class of sets is shown to play a crucial role. The bounds are illustrated on various examples.

Published in at http://dx.doi.org/10.1214/10-AOS817 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Finding large average submatrices in high dimensional data
• Searching for a trail of evidence in a maze
• Negative association in uniform forests and connected graphs

Cited by in corpus (33)

• Optimal detection of sparse principal components in high dimension
• Detection of an anomalous cluster in a network
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Computational Lower Bounds for Sparse PCA
• Detection of correlations
• Nonparametric Detection of Geometric Structures over Networks
• Detecting positive correlations in a multivariate sample
• Efficient Minimax Signal Detection on Graphs
• On the Optimality of Kernel-Embedding Based Goodness-of-Fit Tests
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation
• Phase Transitions for High Dimensional Clustering and Related Problems
• Universality of Computational Lower Bounds for Submatrix Detection
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Energy Landscape for large average submatrix detection problems in Gaussian random matrices
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Adaptive Inferential Method for Monotone Graph Invariants
• High-Temperature Structure Detection in Ferromagnets
• Non-asymptotic detection of two-component mixtures with unknown means
• Quickest Detection of Dynamic Events in Networks
• Distribution-Free Detection of Structured Anomalies: Permutation and Rank-Based Scans
• Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions
• On Minimax Exponents of Sparse Testing
• Lattice partition recovery with dyadic CART
• Some superconcentration inequalities for extrema of stationary Gaussian Processes
• Global Testing Against Sparse Alternatives under Ising Models
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
• A Kernel-Based Nonparametric Test for Anomaly Detection over Line Networks
• Detecting Anomalous Activity on Networks with the Graph Fourier Scan Statistic
• Optimal partition recovery in general graphs
• Sharp Signal Detection Under Ferromagnetic Ising Models
• On the Necessity of Irrelevant Variables