PaperlayerView exact revision on arXiv

Source-linked AI summary

The Geometry of Nonparametric Filament Estimation

Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, Larry Wasserman

arXiv:1003.5536v2math.STastro-ph.IMstat.TH

TL;DR

The paper studies how to estimate filamentary structure from planar point-process data. It uses computational geometry to build nonparametric filament estimators from support-boundary estimates, showing a medial-axis representation under a thickness condition and corresponding convergence results.

  • Problem

    The paper addresses estimating one-dimensional filaments from planar point-process data, a structure arising in applications such as astronomy, geology, and medicine.

    Source: §1 · pp. 3–4

  • Method

    The method connects computational geometry with nonparametric estimation by converting an estimate of the distribution support’s boundary into a filament estimator.

    Source: §1 · p. 3, §3.2 · p. 11

  • Results

    When σ < ∆(f), the filament is the medial axis of the support, and boundary-estimator convergence rates carry over to filament estimators.

    Source: §1 · p. 5

  • Takeaways & Limitations

    The approach provides a simple two-stage route—construct a fitted-value set, then extract a curve—with reasonably fast convergence rates.

    Source: §5 · p. 25

    Optimal rates remain unknown and depend critically on the noise distribution; when curves are not separated by more than 2σ, the entire curve cannot be claimed well estimated.

    Source: §3.3 · p. 16, §5 · p. 25

Abstract

from arXiv · show

We consider the problem of estimating filamentary structure from planar point process data. We make some connections with computational geometry and we develop nonparametric methods for estimating the filaments. We show that, under weak conditions, the filaments have a simple geometric representation as the medial axis of the data distribution's support. Our methods convert an estimator of the support's boundary into an estimator of the filaments. We also find the rates of convergence of our estimators.

1. Introduction.

Filaments are one-dimensional curves with applications across fields, and the paper connects their estimation to computational geometry. It proposes simple nonparametric estimators and establishes geometric representation and convergence results.

1. Introduction.

  • Existing approaches include principal curves, beamlets, parametric models, manifold learning, gradient-based methods, and computational geometry methods.Examples include principal curves by Hastie and Stuetzle (1989) and computational geometry methods by Dey (2006).Source: §1 · p. 3
  • The proposed nonparametric estimators are simpler than Cheng et al. (2005), with weaker assumptions, a more stringent loss, and faster convergence rates.The paper identifies Cheng et al. (2005) as an exception to its claim of computationally simple, consistent methods with convergence rates.Source: §1 · p. 3
  • The optimal convergence rates appear unknown, and the proposed methods are unlikely to be minimax optimal despite being simple to compute.The rates depend critically on features of the noise distribution F.Source: §1 · p. 3
  • When σ < ∆(f), the filament equals the medial axis of the support of Y’s distribution.The paper also shows that support-boundary estimators yield filament estimators with the same Hausdorff convergence rate, and that close fitted-value sets can yield close curves.Source: §1 · p. 5
  • Boundary estimators transfer to filament estimators at the same Hausdorff convergence rate, and fitted-value sets contain and remain close to the filament.The paper also describes extracting curves from those sets that are Hausdorff-close to the true filament.Source: §1 · p. 5

2. The Model.

The model treats observed planar points as noisy samples from one or more curves, with extensions for background clutter. Its thickness condition captures both curvature and proximity to self-intersection.

2. The Model.

  • For a single filament, observations have the form Yi = f(Ui) + ϵi, with latent Ui drawn from H and noise ϵi drawn from F.The filament graph is contained in a compact set, and the loss is Hausdorff distance between sets.Source: §2 · pp. 5–6
  • The sampling distribution H has a density bounded above and away from zero, while the noise has bounded continuous density supported on B(0, σ).The noise density is symmetric and has specified boundary behavior near the support boundary.Source: §2 · p. 7
  • The model assumes σ < ∆(f), where thickness measures curvature and how close the curve comes to self-intersecting.Thickness is the largest radius of a ball that can roll freely around the curve; balls larger than ∆ can meet another part of the curve.Source: §2 · pp. 6–7
  • The model extends to multiple curves and to a mixture with uniform background clutter; the paper assumes no clutter until Section 3.5.Multiple curves can also be modeled by allowing f to be piecewise continuous.Source: §2 · p. 8

3. Estimation.

Under thickness conditions, a filament can be represented geometrically by the support’s medial axis, and estimators of the support boundary can be converted into filament estimators. The section develops boundary-based methods and establishes their convergence behavior.

3.1. Some Backgound on Geometry.

  • For closed curves with σ < ∆(f), the filament equals the support’s medial axis; for open curves, equality also requires σ < ||f(1) − f(0)||/2.Without that additional open-curve condition, the filament is contained in the medial axis.Source: §3.1 · p. 10
  • Because the medial axis can change completely under small support perturbations, the EDT characterization and its estimator provide an alternative route to locating the filament.The filament is the set of support points whose distance to the boundary equals σ; the estimated maximizer is within 2ϵ of the medial axis when the EDT error is at most ϵ.Source: §3.1 · pp. 10–11

3.2. Estimating Boundaries.

  • The union-of-balls support estimator yields a boundary estimator with rate rn = C(log n/n)^(1/(2+α)) under the stated support and density conditions.The density may approach zero at the boundary, provided q(y) ≥ C d(y, ∂S)^α; the estimated support contains S almost surely for all sufficiently large n.Source: §3.2 · pp. 11–12

3.3. From Boundaries to Filaments.

  • The EDT estimator selects support points whose estimated boundary distance is within 2ϵ of its maximum, and its fitted set lies within 4ϵ of the filament when the boundary error is at most ϵ.The EDT curve-extraction method can produce a curve whose Hausdorff error is bounded by a constant times the boundary-estimation error.Source: §3.3 · p. 13, §3.4 · p. 17
  • The medial estimator connects each point on one estimated boundary component to its nearest point on the other and uses the segment midpoint; completing its gaps yields a simple closed curve with Hausdorff error OP(rn).The raw medial estimator converges more slowly than the EDT estimator, but the extracted curve has rate rn rather than √rn.Source: §3.3 · pp. 14–16
  • For finitely many filaments separated by more than 2σ and each satisfying σ < minj ∆(fj), either procedure estimates the filaments at rate rn.When the separation condition fails, the paper does not claim accurate estimation of the entire curve, though well-separated portions can be estimated.Source: §3.3 · p. 16
  • The reported rates are log n/n for the EDT estimator and (log n/n)^(1/4) for the medial estimator.The section also states that extracting a curve from medial fitted values improves its rate to rn rather than √rn.Source: §3.3 · pp. 15–16

3.4. Extracting a curve from EDT estimator.

  • The EDT extraction argument uses the fitted set’s proximity to the filament: an open-curve path crosses each fiber, while a closed-curve path with winding number 1 does so.In either case, the resulting curve is within 4ϵ of the filament when the fitted set is within 4ϵ of it.Source: §3.4 · p. 17

1. Find end points bx0 and bx1 satisfying

The extraction procedure turns a fitted set into a curve, while decluttering classifies points before the filament algorithms are applied.

1. Find end points bx0 and bx1 satisfying

  • The open-curve procedure selects endpoints using path lengths in a minimum spanning tree, then joins them by a path through the fitted set.A ξ-net supports the tree construction; relaxation is optional and used when a smooth curve is desired.Source: §1 · pp. 17–19
  • For closed curves, the algorithm identifies a region around a selected point, finds endpoints on its boundary, and joins them within that region.The general-curve case uses this region to decide whether to apply the closed-curve algorithm or join two open-curve components.Source: §1 · p. 18
  • When the estimated support boundary is within ϵ of the true boundary, extracted closed and open curves are within 4ϵ and 16ϵ, respectively, of the true filament.The stated result assumes dH(∂S, c ∂S) ≤ ϵ.Source: §1 · p. 19

3.5. Decluttering.

  • Decluttering treats observations as a mixture of filament points and uniform background points, then classifies them using a density estimate.The estimated classifier marks points as filament when the density estimate is at least twice the background density; the prior Bayes rule is not identifiable.Source: §3.5 · p. 19
  • The paper illustrates decluttering in examples but leaves investigation of its properties beyond its scope.The authors report that the procedure appears to perform well in practice.Source: §3.5 · p. 20

4. Examples.

The examples apply decluttering and two filament estimators to simulated datasets, including separated, intersecting, and multiple-filament cases. Accuracy is strongest away from intersections and close approaches, where the stated curvature condition can fail.

4. Examples.

  • The simulations covered two smooth filaments that were separated or intersecting, plus a case with 12 open filaments and several intersections.Only the first dataset completely satisfied the paper’s conditions because intersections violate the radius-of-curvature condition.Source: §4 · p. 20
  • Decluttering appeared to separate filament points from clutter well in the first two datasets, each containing two filaments and 500 background-clutter points.The first two datasets had 1500 points apiece.Source: §4 · p. 20
  • For the first dataset, EDT and medial estimates were very close to the true filaments; in the intersecting second dataset, the medial estimate missed the filament near the intersection.The medial estimate became more accurate away from the intersection and was described as satisfactory despite the violated curvature condition.Source: §4 · pp. 20, 22
  • In the 12-filament example, decluttering marked 989 of 1310 points as filament, including 34 clutter points, and marked 321 as clutter, including 5 filament points.Estimates were accurate for nonintersecting filaments but less satisfactory for intersecting or closely spaced filaments, where the radius-of-curvature condition fails.Source: §4 · p. 22

5. Discussion.

The discussion emphasizes the simplicity and non-minimax status of the estimators, compares their rates with Cheng et al. (2005), and identifies noise assumptions and open extensions.

5. Discussion.

  • The second and third examples show true curves and distribution support, data and decluttering, then EDT and medial estimators.In both figures, the top line shows curves/support and data; the center line shows clutter points and decluttered data; the bottom line shows the two estimators.Source: Figure 11 · p. 23, Figure 12 · p. 24
  • The convergence rate depends critically on the noise distribution, and the estimators are unlikely to be minimax optimal.The paper describes the problem as essentially deconvolution because the latent variables ξ_i = f(U_i) are unobserved and corrupted by noise.Source: §5 · p. 25
  • The estimators are simple but not minimax; they form fitted values close to the filament and then extract a curve.The paper gives two approaches for obtaining fitted values and a curve-extraction method for each.Source: §5 · p. 25
  • The analysis assumes compactly supported noise; without compact support, the methods’ behavior changes substantially.Compact support is described as reasonable for many applications.Source: §5 · p. 25
  • Compared with Cheng et al. (2005), the method uses weaker conditions and achieves a faster rate when α is not too large, with Hausdorff distance as the loss.Cheng et al. report fitted values at OP((log n/n)^(1/8)); their paper implicitly assumes α = 0.Source: §5 · p. 25
  • General minimax rates and extensions to higher dimensions, weaker smoothness conditions, noncompact noise, and data-driven tuning remain under investigation.The authors also list relaxing the constant-σ condition, comparing with beamlets, and studying decluttering’s theoretical properties as ongoing work.Source: §5 · pp. 22, 25

6. Supplementary Material.

The supplementary material establishes properties and bounds used in the filament and medial-axis estimation arguments. It also develops technical results for open-curve endpoints and boundary estimation, including conditions for separating estimated boundary pieces and results for connected-component boundary estimators.

6.1. Proofs.

  • Near the boundary, the density is bounded below proportionally to d(y,∂S)^(β+1/2).Source: §6.1 · pp. 26–27
  • The proofs establish Γ_f=M(S) for closed filaments and for open filaments whose endpoints are more than 2σ apart.For open curves, the support decomposes into a tube and two disjoint end caps, and the tube is the union of disjoint fibers.Source: §6.1 · pp. 27–29
  • For points y on M(S), d(y,∂S)=σ; off the medial axis, d(y,∂S)<σ, with σ=d(y,M(S))+Λ(y) in the stated fiber representation.Source: §6.1 · p. 29
  • The support is (χ, λ)-standard with χ=1/4 and λ=σ, and it is expandable because exterior balls of radius Δ−σ roll freely.Source: §6.1 · p. 30
  • Points in bΓ lie within 4ε of the medial axis M.The proof also establishes M ⊂ bΓ.Source: §6.1 · p. 30
  • The boundary curves have thickness Δ−σ, with outer and inner critical-ball radii Δ−σ and Δ+σ, respectively.Source: §6.1 · p. 35
  • The fitted values lie within εn of M(S), and every point of M(S) has a fitted value within O(εn), including after linear completion.The proof bounds the distance between the projected chord and its fitted segment by O(εn), then uses the rolling-ball condition to bound the distance from the medial-axis point to the chord.Source: §6.1 · p. 38

6.1. Proofs. / 6.3. Estimating the Endpoints.

  • The closed-curve algorithm yields a closed curve within the estimated region with winding number 1, while open-curve endpoint estimates are within 16ε of the true endpoints.For Theorem 15, the closed-curve construction closes a path inside the estimated region with absolute winding number 1 around an interior point. The endpoint bound follows from Theorem 25.Source: §6.1 · pp. 38–39, §6.3 · pp. 45–46

6.1. Proofs.

  • For compact connected S, any segment from a point in S to a point outside S intersects ∂S; a ball meeting S but not ∂S lies wholly in S.These two properties are stated in Lemma 21 and established using the first boundary-crossing point and convexity of the ball.Source: §6.1 · p. 39

6.2. Open Curves.

  • Theorem 22 bounds the open-curve end-cap regions by neighborhoods of the endpoint sets, with the stated constants depending on a, ϕ, σ, and ∆.It gives E0(cε) ⊂ V0(a√ε) and E1(cε) ⊂ V1(a√ε); conversely, the V regions lie within b√ε enlargements or d√ε neighborhoods of the corresponding endpoint sets.Source: §6.2 · p. 40

6.3. Estimating the Endpoints.

  • For u∈Γ, the fiber intersection with bΓ is a connected line segment when f is closed, or when f is open and u lies at least 2ε from either endpoint.Source: §6.3 · p. 43

6.4. Estimating the Boundaries.

  • When σ ≤ ||f(1) − f(0)||/5, the estimated endpoint boundary pieces are separated by more than 2bσ + 2cε.Theorem 26 assumes boundary Hausdorff error at most ε, endpoint errors at most Cε, a connected estimated boundary, and c ≥ C + 1; Theorem 27 applies under those assumptions.Source: §6.4 · pp. 46–47
  • Theorem 28’s boundary estimators have two connected components, c∂S0 and c∂S1, and the estimated boundary is within c2√ϵ Hausdorff distance of ∂S0.The proof also bounds the approximation near the endpoints of the boundary curve by a constant times √ϵ.Source: §6.4 · pp. 48–49
  • The medial estimator derived from c∂S0 and c∂S1 satisfies the results of Theorem 10.Theorem 29 obtains this by combining the preceding results.Source: §6.4 · p. 49
Loading 1003.5536v2…