Online citations, reference lists, and bibliographies.
Please confirm you are human
(Sign Up for free to never see this)
← Back to Search

Exact Asymptotics For The Scan Statistic And Fast Alternatives

James Sharpnack, E. Arias-Castro
Published 2014 · Mathematics

Save to my Library
Download PDF
Analyze on Scholarcy
Share
We consider the problem of detecting a rectangle of activation in a grid of sensors in d-dimensions with noisy measurements. This has applications to massive surveillance projects and anomaly detection in large datasets in which one detects anomalously high measurements over rectangular regions, or more generally, blobs. Recently, the asymptotic distribution of a multiscale scan statistic was established in (Kabluchko, 2011) under the null hypothesis, using non-constant boundary crossing probabilities for locally-stationary Gaussian random fields derived in (Chan and Lai, 2006). Using a similar approach, we derive the exact asymptotic level and power of four variants of the scan statistic: an oracle scan that knows the dimensions of the activation rectangle; the multiscale scan statistic just mentioned; an adaptive variant; and an epsilon-net approximation to the latter, in the spirit of (Arias-Castro, 2005). This approximate scan runs in time near-linear in the size of the grid and achieves the same asymptotic power as the adaptive scan. We complement our theory with some numerical experiments.
This paper references
10.1090/S0002-9947-1969-0250367-X
Upcrossing probabilities for stationary Gaussian processes
J. Pickands (1969)
10.1016/S1361-8415(96)80007-7
Deformable models in medical image analysis: a survey
T. McInerney (1996)
10.1002/jmri.1125
Texture detection of simulated microcalcification susceptibility effects in magnetic resonance imaging of breasts
D. James (2001)
10.1090/S0002-9947-1973-0322943-8
Asymptotic properties of Gaussian random fields
C. Qualls (1973)
10.1007/978-1-4614-6170-8_100087
Scan Statistics
(2014)
10.1097/00124784-200107060-00006
The emerging science of very early detection of disease outbreaks.
M. Wagner (2001)
Scan statistics
J. Glaz (2001)
10.1002/SIM.2490
An elliptic spatial scan statistic.
M. Kulldorff (2006)
10.1080/03610929708831995
A spatial scan statistic
M. Kulldorff (1997)
10.1214/09-AOS732
Optimal and fast detection of spatial clusters with scan statistics
Guenther Walther (2010)
10.1214/AOS/1074290328
Maximal meaningful events and applications to image analysis
A. Desolneux (2003)
10.1109/MC.2004.103
Radiation detection with distributed sensor networks
S. Brennan (2004)
10.1016/J.SPA.2010.11.007
Extremes of the standardized Gaussian noise
Z. Kabluchko (2010)
10.3201/EID1005.030646
Syndromic surveillance in public health practice, New York City.
R. Heffernan (2004)
10.1214/AOP/1176991491
Two moments su ce for Poisson approx-imations: the Chen-Stein method
R. Arratia (1989)
10.1109/ICPR.2002.1044812
A method for detecting artificial objects in natural environments
Y. Caron (2002)
10.1214/009117905000000378
Maxima of asymptotically Gaussian random fields and moderate deviation approximations to boundary crossing probabilities of sums of random variables with multidimensional indices
H. Chan (2006)
10.1214/AOS/1176324466
Using the Generalized Likelihood Ratio Statistic for Sequential Detection of a Change-Point
D. Siegmund (1995)
10.1007/3-540-45786-0_46
Automatic Brain and Tumor Segmentation
Nathan Moon (2002)
10.1080/01621459.1965.10480810
The Distribution of the Size of the Maximum Cluster of Points on a Line
J. Naus (1965)
10.1109/TIT.2005.850056
Near-optimal detection of geometric objects by fast multiscale methods
Ery Arias-Castro (2005)
Overview of sensor networks
David Cruller (2004)
10.1239/JAP/1165505213
On the asymptotic distribution of the discrete scan statistic
M. V. Boutsikas (2006)
10.1214/aop/1039548374
Maxima of partial sums indexed by geometrical structures
Tiefang Jiang (1999)
Markov Processes, Gaussian Processes, and Local Times
M. Marcus (2006)
10.1198/106186006X112396
Evaluation of Spatial Scan Statistics for Irregularly Shaped Clusters
L. Duczmal (2006)
10.1214/10-AOS839
Detection of an anomalous cluster in a network
E. Arias-Castro (2011)
10.1038/nm1152
Advances in detecting and responding to threats from bioterrorism and emerging infectious disease
L. Rotz (2004)
10.1016/S0034-4257(96)00117-4
Fire detection and growth monitoring using a multitemporal technique on AVHRR mid-infrared and thermal channels
D. Pozo (1997)



This paper is referenced by
Optimal Inference with a Multidimensional Multiscale Statistic
P. Datta (2018)
10.1214/18-EJS1512
Detection of Sparse Mixtures: Higher Criticism and Scan Statistic
E. Arias-Castro (2018)
Variational estimators in statistical multiscale analysis
Housen Li (2016)
Signal Processing over graphs
James Sharpnack (2014)
10.3150/16-BEJ913
Extrema of rescaled locally stationary Gaussian fields on manifolds
Wanli Qiao (2018)
On the Asymptotic Distribution of the Scan Statistic for Point Clouds
Andrew Ying (2019)
10.1214/18-aos1806
Multidimensional multiscale scanning in Exponential Families: Limit theory and statistical consequences
Claudia Konig (2018)
Template Matching and Change Point Detection by M-estimation.
Ery Arias-Castro (2020)
On Minimax Exponents of Sparse Testing
R. Mukherjee (2020)
10.1214/17-AIHP832
Variational Multiscale Nonparametric Regression: Smooth Functions
M. Grasmair (2015)
Asymptotic Procedures for a Change-Point Analysis of Random Field
Béatrice Bucchia (2016)
10.1214/17-AOS1669
Multiscale scanning in inverse problems
K. Proksch (2016)
Distribution du score local pour la détection de régions atypiques au sein de séquences
Sabine Mercier (2018)
10.1080/01621459.2017.1286240
Distribution-Free Detection of Structured Anomalies: Permutation and Rank-Based Scans
Ery Arias-Castro (2015)
10.1007/978-3-030-34413-9_11
Photonic Imaging with Statistical Guarantees: From Multiscale Testing to Multiscale Estimation
A. Munk (2020)
Extrema of locally stationary Gaussian fields on growing manifolds
Wanli Qiao (2015)
Learning Patterns for Detection with Multiscale Scan Statistics
James Sharpnack (2018)
Narrowest Significance Pursuit: inference for multiple change-points in linear models
P. Fryzlewicz (2020)
On the Asymptotic Distribution of the Scan Statistic for Empirical Distributions.
Andrew Ying (2020)
On high-dimensional support recovery and signal detection
ET Ervin Tánczos (2012)
Calibrating the scan statistic: finite sample performance vs. asymptotics
Guenther Walther (2020)
10.1017/jpr.2017.36
Limit laws on extremes of nonhomogeneous Gaussian random fields
Z. Tan (2017)
Semantic Scholar Logo Some data provided by SemanticScholar