TY - JOUR
T1 - Convergence of Algorithms for Reconstructing Convex Bodies and Directional Measures
AU - Gardner, Richard
AU - Kiderlen, Markus
AU - Milanfar, Peyman
PY - 2006
Y1 - 2006
N2 - We investigate algorithms for reconstructing a convex body K in Rn from noisy measurements of its support function or its brightness function in k directions u1, . . . , uk. The key idea of these algorithms is to construct a convex polytope Pk whose support function (or brightness function) best approximates the given measurements in the directions u1, . . . , uk (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, Pk tends to K in the Hausdor metric as k ! 1. Here some mild assumptions on the sequence (ui) 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 L2 metric and then transferred to the Hausdor 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 fibre process from noisy measurements of its rose of intersections in k directions u1, . . . , uk. 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.
AB - We investigate algorithms for reconstructing a convex body K in Rn from noisy measurements of its support function or its brightness function in k directions u1, . . . , uk. The key idea of these algorithms is to construct a convex polytope Pk whose support function (or brightness function) best approximates the given measurements in the directions u1, . . . , uk (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, Pk tends to K in the Hausdor metric as k ! 1. Here some mild assumptions on the sequence (ui) 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 L2 metric and then transferred to the Hausdor 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 fibre process from noisy measurements of its rose of intersections in k directions u1, . . . , uk. 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.
KW - Convex body, convex polytope, support function, brightness function, surface area measure, least squares, set-valued estimator, cosine transform, algorithm, geometric tomography, stereology, fiber process, directional measure, rose of intersections.
KW - Convex body, convex polytope, support function, brightness function, surface area measure, least squares, set-valued estimator, cosine transform, algorithm, geometric tomography, stereology, fiber process, directional measure, rose of intersections.
M3 - Journal article
SN - 0090-5364
VL - 34
SP - 1331
EP - 1374
JO - Annals of Statistics
JF - Annals of Statistics
IS - 3
ER -