Adaptive multiscale detection of filamentary structures embedded in a background of uniform random points
Ery Arias-Castro, David L. Donoho, Xiaoming Sharon Huo · 2003
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 α-norm bounded by β. An asymptotic detection threshold exists in this problem; for a constant T−(α, β)> 0, if the number of points sampled from the curve is smaller than T−(α, β)n 1/(1+α) , 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 α or β in advance, provided that the number of points on the curve exceeds T∗(α, β)n 1/(1+α). 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