×

Convergence of algorithms for reconstructing convex bodies and directional measures. (English) Zbl 1097.52503

Summary: 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,\dots,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,\dots,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 \(k\to\infty\). 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,\dots,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.

MSC:

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

References:

[1] Bourgain, J. and Lindenstrauss, J. (1988). Projection bodies. Geometric Aspects of Functional Analysis . Lecture Notes in Math. 1317 250–270. Springer, Berlin. · Zbl 0645.52002
[2] Bourgain, J. and Lindenstrauss, J. (1988). Distribution of points on spheres and approximation by zonotopes. Israel J. Math. 64 25–31. · Zbl 0667.52001
[3] Bronshtein, E. M. (1976). \(\ee\)-entropy of convex sets and functions. Siberian Math. J. 17 393–398. · Zbl 0354.54026
[4] Campi, S. (1988). Recovering a centred convex body from the areas of its shadows: A stability estimate. Ann. Mat. Pura Appl. ( 4 ) 151 289–302. · Zbl 0657.52001
[5] Campi, S., Colesanti, A. and Gronchi, P. (1995). Convex bodies with extremal volumes having prescribed brightness in finitely many directions. Geom. Dedicata 57 121–133. · Zbl 0838.52011
[6] Dudley, R. M. (1968). Distances of probability measures and random variables. Ann. Math. Statist. 39 1563–1572. · Zbl 0169.20602
[7] Dudley, R. M. (2002). Real Analysis and Probability , rev. reprint. Cambridge Univ. Press. · Zbl 1023.60001
[8] Fisher, N. I., Hall, P., Turlach, B. and Watson, G. S. (1997). On the estimation of a convex set from noisy data on its support function. J. Amer. Statist. Assoc. 92 84–91. JSTOR: · Zbl 0890.62028
[9] Fortet, R. and Mourier, E. (1953). Convergence de la répartition empirique vers la répartition théorique. Ann. Sci. École Norm. Sup. ( 3 ) 70 267–285. · Zbl 0053.09601
[10] Gardner, R. J. (1995). Geometric Tomography . Cambridge Univ. Press. · Zbl 1042.52501
[11] Gardner, R. J., Kiderlen, M. and Milanfar, P. (2005). Extended version of “Convergence of algorithms for reconstructing convex bodies and directional measures.” Available at www.ac.wwu.edu/ gardner. · Zbl 1097.52503
[12] Gardner, R. J. and Milanfar, P. (2001). Shape reconstruction from brightness functions. In Proc. SPIE Conference on Advanced Signal Processing Algorithms Architectures and Implementations XI 4474 (F. T. Luk, ed.) 234–245. SPIE, Bellingham, WA.
[13] Gardner, R. J. and Milanfar, P. (2003). Reconstruction of convex bodies from brightness functions. Discrete Comput. Geom. 29 279–303. · Zbl 1035.52001
[14] Gregor, J. and Rannou, F. R. (2002). Three-dimensional support function estimation and application for projection magnetic resonance imaging. Internat. J. Imaging Systems and Technology 12 43–50.
[15] Groemer, H. (1996). Geometric Applications of Fourier Series and Spherical Harmonics . Cambridge Univ. Press. · Zbl 0877.52002
[16] Hall, P. and Turlach, B. (1999). On the estimation of a convex set with corners. IEEE Trans. Pattern Analysis and Machine Intelligence 21 225–234.
[17] Hug, D. and Schneider, R. (2002). Stability results involving surface area measures of convex bodies. Rend. Circ. Mat. Palermo ( 2 ) Suppl. 70 , part II 21–51. · Zbl 1113.52013
[18] Ikehata, M. and Ohe, T. (2002). A numerical method for finding the convex hull of polygonal cavities using the enclosure method. Inverse Problems 18 111–124. · Zbl 0992.35118
[19] Karl, W. C., Kulkarni, S. R., Verghese, G. C. and Willsky, A. S. (1996). Local tests for consistency of support hyperplane data. J. Math. Imaging Vision 6 249–267. · Zbl 05476697
[20] Kiderlen, M. (2001). Non-parametric estimation of the directional distribution of stationary line and fibre processes. Adv. in Appl. Probab. 33 6–24. · Zbl 0998.62080
[21] Lele, A. S., Kulkarni, S. R. and Willsky, A. S. (1992). Convex-polygon estimation from support-line measurements and applications to target reconstruction from laser-radar data. J. Opt. Soc. Amer. A 9 1693–1714.
[22] Mammen, E., Marron, J. S., Turlach, B. A. and Wand, M. P. (2001). A general projection framework for constrained smoothing. Statist. Sci. 16 232–248. · Zbl 1059.62535
[23] Männle, S. (2002). Ein Kleinste–Quadrat–Schätzer des Richtungsmaßes für stationäre Geradenprozesse. Masters thesis, Univ. Karlsruhe, Germany.
[24] Matoušek, J. (1996). Improved upper bounds for approximation by zonotopes. Acta Math. 177 55–73. · Zbl 0887.52003
[25] Pollard, D. (1984). Convergence of Stochastic Processes . Springer, New York. · Zbl 0544.60045
[26] Poonawala, A., Milanfar, P. and Gardner, R. J. (2006). Shape estimation from support and diameter functions. J. Math. Imaging Vision 24 229–244. · Zbl 1478.94075
[27] Prince, J. L. and Willsky, A. S. (1990). Reconstructing convex sets from support line measurements. IEEE Trans. Pattern Analysis and Machine Intelligence 12 377–389.
[28] Schneider, R. (1993). Convex Bodies : The Brunn–Minkowski Theory . Cambridge Univ. Press. · Zbl 0798.52001
[29] Schneider, R. and Weil, W. (2000). Stochastische Geometrie . Teubner, Stuttgart. · Zbl 0964.52009
[30] Stoyan, D., Kendall, W. S. and Mecke, J. (1995). Stochastic Geometry and Its Applications , 2nd ed. Wiley, New York. · Zbl 0622.60019
[31] van de Geer, S. (1990). Estimating a regression function. Ann. Statist. 18 907–924. · Zbl 0709.62040
[32] van de Geer, S. (2000). Applications of Empirical Process Theory . Cambridge Univ. Press. · Zbl 0953.62049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.