Convergence of algorithms for reconstructing convex bodies and directional measures

DOI10.1214/009053606000000335MaRDI QIDQ2500455zbMATH OpenOpenAlexFDO

Authors Markus Kiderlen, Peyman Milanfar, Richard J. Gardner

Publication date 24 August 2006

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

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

zbMATH Keywords

algorithmbrightness functionconvex bodyconvex polytopecosine transformfiber processgeometric tomographyleast squaresrose of intersectionsset-valued estimatorstereologysupport functionsurface area measure

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Geometric probability and stochastic geometry (60D05) Stationary stochastic processes (60G10) Inference from spatial processes (62M30) Algorithms for approximation of functions (65D15)

Abstract: We investigate algorithms for reconstructing a convex body $K$ in $mathbb{R}^n$ from noisy measurements of its support function or its brightness function in $k$ directions $u_1,\mathrm{...},u_k$. The key idea of these algorithms is to construct a convex polytope $P_k$ whose support function (or brightness function) best approximates the given measurements in the directions $u_1,\mathrm{...},u_k$ (in the least squares sense). The measurement errors are assumed to be stochastically independent and Gaussian. It is shown that this procedure is (strongly) consistent, meaning that, almost surely, $P_k$ tends to $K$ in the Hausdorff metric as $koinfty$. Here some mild assumptions on the sequence $(u_i)$ of directions are needed. Using results from the theory of empirical processes, estimates of rates of convergence are derived, which are first obtained in the $L_2$ metric and then transferred to the Hausdorff metric. Along the way, a new estimate is obtained for the metric entropy of the class of origin-symmetric zonoids contained in the unit ball. Similar results are obtained for the convergence of an algorithm that reconstructs an approximating measure to the directional measure of a stationary fiber process from noisy measurements of its rose of intersections in $k$ directions $u_1,\mathrm{...},u_k$. Here the Dudley and Prohorov metrics are used. The methods are linked to those employed for the support and brightness function algorithms via the fact that the rose of intersections is the support function of a projection body.

Recommendations

• Reconstruction of convex bodies from brightness functions
• Reconstruction of convex bodies from surface tensors
• Consistency method for measurements of the support function of a convex body in the metric of L_
• An algorithm for reconstructing convex bodies from their projections

Cites work

• A general projection framework for constrained smoothing.
• A numerical method for finding the convex hull of polygonal cavities using the enclosure method
• Convergence de la répartition empirique vers la répartition théorique
• Convergence of algorithms for reconstructing convex bodies and directional measures
• Convergence of stochastic processes
• Convex bodies with extremal volumes having prescribed brightness in finitely many directions
• Distances of Probability Measures and Random Variables
• Distribution of points on spheres and approximation by zonotopes
• epsilon-entropy of convex sets and functions
• Estimating a regression function
• Geometric tomography.
• scientific article; zbMATH DE number 4009416 (Why is no real title available?)
• scientific article; zbMATH DE number 4052453 (Why is no real title available?)
• scientific article; zbMATH DE number 1371329 (Why is no real title available?)
• scientific article; zbMATH DE number 1420699 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• scientific article; zbMATH DE number 967594 (Why is no real title available?)
• Improved upper bounds for approximation by zonotopes
• Local tests for consistency of support hyperplane data.
• Non-parametric estimation of the directional distribution of stationary line and fibre processes
• On the Estimation of a Convex Set From Noisy Data on Its Support Function
• Real Analysis and Probability
• Reconstruction of convex bodies from brightness functions
• Recovering a centred convex body from the areas of its shadows: A stability estimate
• Shape estimation from support and diameter functions
• Stability results involving surface area measures of convex bodies

Cited in

(30)

• Eliciting beliefs
• Adaptive estimation of planar convex sets
• Consistency method for measurements of the support function of a convex body in the metric of L_
• Editorial: Special issue on ``Nonparametric inference under shape constraints
• Methods for estimation of convex sets
• The surface area deviation of the Euclidean ball and a polytope
• Approximation of smooth convex bodies by random polytopes
• Lightness functions
• Surface area deviation between smooth convex bodies and polytopes
• Fitting tractable convex sets to support function evaluations
• Shape estimation from support and diameter functions
• Convergence of algorithms for reconstructing convex bodies and directional measures
• A solution to Hammer's X-ray reconstruction problem
• Adaptation in multivariate log-concave density estimation
• A concentration inequality for random polytopes, Dirichlet-Voronoi tiling numbers and the geometric balls and bins problem
• Reconstruction of convex bodies from surface tensors
• Error bounds for consistent reconstruction: random polytopes and coverage processes
• Reconstruction of \(n\)-dimensional convex bodies from surface tensors
• Optimal rates of convergence for convex set estimation from support functions
• Asymptotic properties of the approximate inverse estimator for directional distributions
• Moments of the distribution of distance
• Estimation of the mean normal measure from flat sections
• Phase retrieval for characteristic functions of convex bodies and reconstruction from covariograms
• SL(n)-covariantL_p-Minkowski valuations
• Reconstruction problems of convex bodies from surface area measures and lightness functions
• Learning Polytopes with Fixed Facet Directions
• Reconstruction problems of convex bodies from even L_p surface area measures
• On length measures of planar closed curves and the comparison of convex shapes
• Stability of the reverse Blaschke-Santaló inequality for zonoids and applications
• Estimating an even spherical measure from its sine transform.

This page was built for publication: Convergence of algorithms for reconstructing convex bodies and directional measures

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