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

DOI10.1214/009053605000000787MaRDI QIDQ2493555zbMATH OpenOpenAlexFDO

Authors Ery Arias-Castro, David Donoho, Xiaoming Huo

Publication date 21 June 2006

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

Full work available at URL https://arxiv.org/abs/math/0605513

zbMATH Keywords

beamletsErdős-Rényi lawsgood continuationmultiscale geometric analysispattern recognitionruns test

Mathematics Subject Classification ID

Applications of graph theory (05C90) Nonparametric hypothesis testing (62G10) Asymptotic properties of nonparametric inference (62G20) Inference from spatial processes (62M30)

Abstract: 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 $$. An asymptotic detection threshold exists in this problem; for a constant $$, if the number of points sampled from the curve is smaller than $$, 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 $$ in advance, provided that the number of points on the curve exceeds $$. This algorithm therefore has an optimal detection threshold, up to a factor $T_{\ast }/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 $mathbf{H}_0$ whenever some such subgraph contains a path that connects many consecutive significant counts.

Recommendations

• An algorithm for automatic curve detection
• On the path density of a gradient field
• Connect the dots: how many random points can a regular curve pass through?
• The geometry of nonparametric filament estimation
• Detectability of convex-shaped objects in digital images, its fundamental limit and multiscale analysis

Cites work

• Adapting to Unknown Smoothness via Wavelet Shrinkage
• CART and best-ortho-basis: a connection
• Connect the dots: how many random points can a regular curve pass through?
• scientific article; zbMATH DE number 1714595 (Why is no real title available?)
• scientific article; zbMATH DE number 2177599 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 499496 (Why is no real title available?)
• Maximal meaningful events and applications to image analysis
• Meaningful alignments
• Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
• Quantifying curvelike structures of measures by usingL2 Jones quantities
• Rectifiable sets and the traveling salesman problem
• The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches
• The statistical theory of shape
• Wedgelets: Nearly minimax estimation of edges

Cited in

(22)

• On the path density of a gradient field
• Multiple penalized principal curves: analysis and computation
• A weighted \(k\)-nearest neighbor density estimate for geometric inference
• Asymptotic confidence regions for density ridges
• NetMix2: unifying network propagation and altered subnetworks
• Posterior contraction and credible sets for filaments of regression functions
• Gromov-Hausdorff approximation of filamentary structures using Reeb-type graphs
• Detection of an anomalous cluster in a network
• Detecting highly oscillatory signals by chirplet path pursuit
• Networks of polynomial pieces with application to the analysis of point clouds and images
• Theoretical analysis of nonparametric filament estimation
• Detecting a path of correlations in a network
• Rates of convergence for robust geometric inference
• The geometry of nonparametric filament estimation
• Automatic locally adaptive smoothing for tree-based set estimation
• NetMix: a network-structured mixture model for reduced-bias estimation of altered subnetworks
• Connect the dots: how many random points can a regular curve pass through?
• Finite size percolation in regular trees
• Confidence regions for filamentary structures
• Multiscale scanning with nuisance parameters
• Optimal detection of multi-sample aligned sparse signals
• Searching for a trail of evidence in a maze

This page was built for publication: Adaptive multiscale detection of filamentary structures in a background of uniform random points

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