Phase retrieval for characteristic functions of convex bodies and reconstruction from covariograms

Bianchi, Gabriele¹ ; Gardner, Richard² ; Kiderlen, Markus³

¹ Dipartimento di Matematica, Università di Firenze, Viale Morgagni 67/A, Firenze, Italy I-50134
² Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063
³ Department of Mathematical Sciences, University of Aarhus, Ny Munkegade, DK–8000 Aarhus C, Denmark

Journal of the American Mathematical Society, Tome 24 (2011) no. 2, pp. 293-343

Résumé

We propose strongly consistent algorithms for reconstructing the characteristic function $1_K$ of an unknown convex body $K$ in $\mathbb {R}^n$ from possibly noisy measurements of the modulus of its Fourier transform $\widehat {1_K}$. This represents a complete theoretical solution to the Phase Retrieval Problem for characteristic functions of convex bodies. The approach is via the closely related problem of reconstructing $K$ from noisy measurements of its covariogram, the function giving the volume of the intersection of $K$ with its translates. In the many known situations in which the covariogram determines a convex body, up to reflection in the origin and when the position of the body is fixed, our algorithms use $O(k^n)$ noisy covariogram measurements to construct a convex polytope $P_k$ that approximates $K$ or its reflection $-K$ in the origin. (By recent uniqueness results, this applies to all planar convex bodies, all three-dimensional convex polytopes, and all symmetric and most (in the sense of Baire category) arbitrary convex bodies in all dimensions.) Two methods are provided, and both are shown to be strongly consistent, in the sense that, almost surely, the minimum of the Hausdorff distance between $P_k$ and $\pm K$ tends to zero as $k$ tends to infinity.

Détail

DOI : 10.1090/S0894-0347-2010-00683-2

Bibliographie

[1] Adler, Robert J., Pyke, Ron Scanning Brownian processes Adv. in Appl. Probab. 1997 295 326

[2] Ahmad, Ibrahim A., Lin, Pi-Erh Fitting a multiple regression function J. Statist. Plann. Inference 1984 163 176

[3] Averkov, Gennadiy, Bianchi, Gabriele Confirmation of Matheron’s conjecture on the covariogram of a planar convex body J. Eur. Math. Soc. (JEMS) 2009 1187 1202

[4] Benassi, Carlo, D’Ercole, Giuliana An algorithm for reconstructing a convex polygon from its covariogram Rend. Istit. Mat. Univ. Trieste 2007 457 476

[5] Bianchi, Gabriele Matheron’s conjecture for the covariogram problem J. London Math. Soc. (2) 2005 203 220

[6] Bianchi, Gabriele The covariogram determines three-dimensional convex polytopes Adv. Math. 2009 1771 1808

[7] Bianchi, Gabriele, Segala, Fausto, VoläIä, Aljoå¡A The solution of the covariogram problem for plane 𝒞²₊ convex bodies J. Differential Geom. 2002 177 198

[8] Billingsley, Patrick Convergence of probability measures 1999

[9] Bourgain, J., Lindenstrauss, J. Projection bodies 1988 250 270

[10] Brandolini, L., Hofmann, S., Iosevich, A. Sharp rate of average decay of the Fourier transform of a bounded set Geom. Funct. Anal. 2003 671 680

[11] Brannen, Noah Samuel The Wills conjecture Trans. Amer. Math. Soc. 1997 3977 3987

[12] Buldygin, V. V., Kozachenko, Yu. V. Metric characterization of random variables and random processes 2000

[13] Cabo, Annoesjka, Baddeley, Adrian Estimation of mean particle volume using the set covariance function Adv. in Appl. Probab. 2003 27 46

[14] Campi, Stefano Recovering a centred convex body from the areas of its shadows: a stability estimate Ann. Mat. Pura Appl. (4) 1988 289 302

[15] Dudley, R. M. Distances of probability measures and random variables Ann. Math. Statist. 1968 1563 1572

[16] Gardner, Richard J. Geometric tomography 2006

[17] Gardner, R. J. The Brunn-Minkowski inequality Bull. Amer. Math. Soc. (N.S.) 2002 355 405

[18] Gardner, Richard J., Gronchi, Paolo, Zong, Chuanming Sums, projections, and sections of lattice sets, and the discrete covariogram Discrete Comput. Geom. 2005 391 409

[19] Gardner, Richard J., Kiderlen, Markus A solution to Hammer’s X-ray reconstruction problem Adv. Math. 2007 323 343

[20] Gardner, Richard J., Kiderlen, Markus, Milanfar, Peyman Convergence of algorithms for reconstructing convex bodies and directional measures Ann. Statist. 2006 1331 1374

[21] Gardner, R. J., Milanfar, Peyman Reconstruction of convex bodies from brightness functions Discrete Comput. Geom. 2003 279 303

[22] Gardner, R. J., Zhang, Gaoyong Affine inequalities and radial mean bodies Amer. J. Math. 1998 505 528

[23] Goodey, Paul, Schneider, Rolf, Weil, Wolfgang On the determination of convex bodies by projection functions Bull. London Math. Soc. 1997 82 88

[24] Hoffmann-Jã¸Rgensen, J. Probability with a view toward statistics. Vol. I 1994

[25] Hu, Tien Chung, Mã³Ricz, F., Taylor, R. L. Strong laws of large numbers for arrays of rowwise independent random variables Acta Math. Hungar. 1989 153 162

[26] Hug, Daniel, Schneider, Rolf Stability results involving surface area measures of convex bodies Rend. Circ. Mat. Palermo (2) Suppl. 2002 21 51

[27] Hurt, Norman E. Phase retrieval and zero crossings 1989

[28] Kiderlen, Markus, Vedel Jensen, Eva B. Estimation of the directional measure of planar random sets by digitization Adv. in Appl. Probab. 2003 583 602

[29] Klibanov, Michael V., Sacks, Paul E., Tikhonravov, Alexander V. The phase retrieval problem Inverse Problems 1995 1 28

[30] Liu, Fon Che On the localization of rectangular partial sums for multiple Fourier series Proc. Amer. Math. Soc. 1972 90 96

[31] Luke, D. Russell, Burke, James V., Lyon, Richard G. Optical wavefront reconstruction: theory and numerical methods SIAM Rev. 2002 169 224

[32] Mallows, C. L., Clark, J. M. C. Linear-intercept distributions do not characterize plane sets J. Appl. Probability 1970 240 244

[33] Matheron, G. Random sets and integral geometry 1975

[34] Matheron, G. La formule de Steiner pour les érosions J. Appl. Probability 1978 126 135

[35] Poonawala, Amyn, Milanfar, Peyman, Gardner, Richard J. Shape estimation from support and diameter functions J. Math. Imaging Vision 2006 229 244

[36] Rosenblatt, Joseph Phase retrieval Comm. Math. Phys. 1984 317 343

[37] Schmitt, Michel On two inverse problems in mathematical morphology 1993 151 169

[38] Schmuckenschlã¤Ger, M. The distribution function of the convolution square of a convex symmetric body in 𝑅ⁿ Israel J. Math. 1992 309 334

[39] Serra, J. Image analysis and mathematical morphology 1984

[40] Schneider, Rolf Convex bodies: the Brunn-Minkowski theory 1993

[41] Tsolomitis, Antonis Convolution bodies and their limiting behavior Duke Math. J. 1997 181 203

[42] Van De Geer, Sara A. Applications of empirical process theory 2000

[43] Van Der Vaart, Aad W., Wellner, Jon A. Weak convergence and empirical processes 1996

[44] Werner, Elisabeth A general geometric construction for affine surface area Studia Math. 1999 227 238