Adaptive multiscale detection of filamentary structures in a background of uniform random points

• 成果类型: Article
• 署名作者: Arias-Castro, Ery; Donoho, David L.; Huo, Xiaoming
• 署名单位: University of California System; University of California San Diego; Stanford University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/009053605000000787
• 发表日期: 2006
• 页码: 326-349
• 关键词: network; curve

摘要

We are given a set of n points that might be uniformly distributed in the unit square [0, 1](2). We wish to test whether the set, although mostly consisting of uniformly scattered points, also contains a small fraction of points sampled from some (a priori unknown) curve with C-alpha-norm bounded by beta. An asymptotic detection threshold exists in this problem; for a constant T_ (alpha, beta) > 0, if the number of points sampled from the curve is smaller than T_(alpha, beta)n(1/(1+alpha)), reliable detection is not possible for large n. We describe a multiscale significant-runs algorithm that can reliably detect concentration of data near a smooth curve, without knowing the smoothness information alpha or 0 in advance, provided that the number of points on the curve exceeds T-*(alpha, beta)n(1/(1+alpha)). This algorithm therefore has an optimal detection threshold, up to a factor T-*/T_. At the heart of our approach is an analysis of the data by counting membership in multiscale multianisotropic strips. The strips will have area 2/n and exhibit a variety of lengths, orientations and anisotropies. The strips are partitioned into anisotropy classes; each class is organized as a directed graph whose vertices all are strips of the same anisotropy and whose edges link such strips to their good continuations. The point-cloud data are reduced to counts that measure membership in strips. Each anisotropy graph is reduced to a subgraph that consist of strips with significant counts. The algorithm rejects Ho whenever some such subgraph contains a path that connects many consecutive significant counts.