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

HTML articles powered by AMS MathViewer

- by Gabriele Bianchi, Richard J. Gardner and Markus Kiderlen PDF
- J. Amer. Math. Soc.
**24**(2011), 293-343 Request permission

## Abstract:

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.## References

- R. J. Adler and R. Pyke, Problem 91–3,
*Inst. Math. Statist. Bull.***20**(1991), 409. - Robert J. Adler and Ron Pyke,
*Scanning Brownian processes*, Adv. in Appl. Probab.**29**(1997), no. 2, 295–326. MR**1450931**, DOI 10.2307/1428004 - Ibrahim A. Ahmad and Pi-Erh Lin,
*Fitting a multiple regression function*, J. Statist. Plann. Inference**9**(1984), no. 2, 163–176. MR**738366**, DOI 10.1016/0378-3758(84)90017-X - Gennadiy Averkov and Gabriele Bianchi,
*Confirmation of Matheron’s conjecture on the covariogram of a planar convex body*, J. Eur. Math. Soc. (JEMS)**11**(2009), no. 6, 1187–1202. MR**2557133**, DOI 10.4171/JEMS/179 - M. Baake and U. Grimm, Homometric model sets and window covariograms,
*Z. Krist.***222**(2007), 54–58. - Carlo Benassi and Giuliana D’Ercole,
*An algorithm for reconstructing a convex polygon from its covariogram*, Rend. Istit. Mat. Univ. Trieste**39**(2007), 457–476. MR**2441634** - Gabriele Bianchi,
*Matheron’s conjecture for the covariogram problem*, J. London Math. Soc. (2)**71**(2005), no. 1, 203–220. MR**2108257**, DOI 10.1112/S0024610704006039 - Gabriele Bianchi,
*The covariogram determines three-dimensional convex polytopes*, Adv. Math.**220**(2009), no. 6, 1771–1808. MR**2493181**, DOI 10.1016/j.aim.2008.11.011 - Gabriele Bianchi, Fausto Segala, and Aljoša Volčič,
*The solution of the covariogram problem for plane $\scr C^2_+$ convex bodies*, J. Differential Geom.**60**(2002), no. 2, 177–198. MR**1938112** - Patrick Billingsley,
*Convergence of probability measures*, 2nd ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999. A Wiley-Interscience Publication. MR**1700749**, DOI 10.1002/9780470316962 - J. Bourgain and J. Lindenstrauss,
*Projection bodies*, Geometric aspects of functional analysis (1986/87), Lecture Notes in Math., vol. 1317, Springer, Berlin, 1988, pp. 250–270. MR**950986**, DOI 10.1007/BFb0081746 - L. Brandolini, S. Hofmann, and A. Iosevich,
*Sharp rate of average decay of the Fourier transform of a bounded set*, Geom. Funct. Anal.**13**(2003), no. 4, 671–680. MR**2006553**, DOI 10.1007/s00039-003-0426-7 - Noah Samuel Brannen,
*The Wills conjecture*, Trans. Amer. Math. Soc.**349**(1997), no. 10, 3977–3987. MR**1373630**, DOI 10.1090/S0002-9947-97-01716-9 - V. V. Buldygin and Yu. V. Kozachenko,
*Metric characterization of random variables and random processes*, Translations of Mathematical Monographs, vol. 188, American Mathematical Society, Providence, RI, 2000. Translated from the 1998 Russian original by V. Zaiats. MR**1743716**, DOI 10.1090/mmono/188 - Annoesjka Cabo and Adrian Baddeley,
*Estimation of mean particle volume using the set covariance function*, Adv. in Appl. Probab.**35**(2003), no. 1, 27–46. In honor of Joseph Mecke. MR**1974301**, DOI 10.1239/aap/1046366097 - Stefano Campi,
*Recovering a centred convex body from the areas of its shadows: a stability estimate*, Ann. Mat. Pura Appl. (4)**151**(1988), 289–302. MR**964515**, DOI 10.1007/BF01762800 - R. M. Dudley,
*Distances of probability measures and random variables*, Ann. Math. Statist.**39**(1968), 1563–1572. MR**230338**, DOI 10.1007/978-1-4419-5821-1_{4} - J. R. Fienup, Phase retrieval algorithms: a comparison,
*Appl. Opt.***21**(1982), 2758–2769. - B. Galerne, Computation of the perimeter of measurable sets via their covariogram. Applications to random sets,
*Image Anal. Stereol.*, to appear. - Richard J. Gardner,
*Geometric tomography*, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 58, Cambridge University Press, New York, 2006. MR**2251886**, DOI 10.1017/CBO9781107341029 - R. J. Gardner,
*The Brunn-Minkowski inequality*, Bull. Amer. Math. Soc. (N.S.)**39**(2002), no. 3, 355–405. MR**1898210**, DOI 10.1090/S0273-0979-02-00941-2 - Richard J. Gardner, Paolo Gronchi, and Chuanming Zong,
*Sums, projections, and sections of lattice sets, and the discrete covariogram*, Discrete Comput. Geom.**34**(2005), no. 3, 391–409. MR**2160045**, DOI 10.1007/s00454-005-1169-z - Richard J. Gardner and Markus Kiderlen,
*A solution to Hammer’s X-ray reconstruction problem*, Adv. Math.**214**(2007), no. 1, 323–343. MR**2348033**, DOI 10.1016/j.aim.2007.02.005 - Richard J. Gardner, Markus Kiderlen, and Peyman Milanfar,
*Convergence of algorithms for reconstructing convex bodies and directional measures*, Ann. Statist.**34**(2006), no. 3, 1331–1374. MR**2278360**, DOI 10.1214/009053606000000335 - R. J. Gardner and Peyman Milanfar,
*Reconstruction of convex bodies from brightness functions*, Discrete Comput. Geom.**29**(2003), no. 2, 279–303. MR**1957233**, DOI 10.1007/s00454-002-0759-2 - R. J. Gardner and Gaoyong Zhang,
*Affine inequalities and radial mean bodies*, Amer. J. Math.**120**(1998), no. 3, 505–528. MR**1623396** - Paul Goodey, Rolf Schneider, and Wolfgang Weil,
*On the determination of convex bodies by projection functions*, Bull. London Math. Soc.**29**(1997), no. 1, 82–88. MR**1416411**, DOI 10.1112/S0024609396001968 - A. Guntuboyina, Lower bounds for the minimax risk using $f$-divergences and applications,
*IEEE Trans. Inform. Theory*, to appear. - J. Hoffmann-Jørgensen,
*Probability with a view toward statistics. Vol. I*, Chapman & Hall Probability Series, Chapman & Hall, New York, 1994. MR**1278485**, DOI 10.1007/978-1-4899-3019-4 - Tien Chung Hu, F. Móricz, and R. L. Taylor,
*Strong laws of large numbers for arrays of rowwise independent random variables*, Acta Math. Hungar.**54**(1989), no. 1-2, 153–162. MR**1015785**, DOI 10.1007/BF01950716 - Daniel Hug and Rolf Schneider,
*Stability results involving surface area measures of convex bodies*, Rend. Circ. Mat. Palermo (2) Suppl.**70**(2002), 21–51. IV International Conference in “Stochastic Geometry, Convex Bodies, Empirical Measures $\&$ Applications to Engineering Science”, Vol. II (Tropea, 2001). MR**1962583** - Norman E. Hurt,
*Phase retrieval and zero crossings*, Mathematics and its Applications, vol. 52, Kluwer Academic Publishers Group, Dordrecht, 1989. Mathematical methods in image reconstruction. MR**1093464**, DOI 10.1007/978-94-010-9608-9 - Markus Kiderlen and Eva B. Vedel Jensen,
*Estimation of the directional measure of planar random sets by digitization*, Adv. in Appl. Probab.**35**(2003), no. 3, 583–602. MR**1990605**, DOI 10.1239/aap/1059486819 - Michael V. Klibanov, Paul E. Sacks, and Alexander V. Tikhonravov,
*The phase retrieval problem*, Inverse Problems**11**(1995), no. 1, 1–28. MR**1313598** - Fon Che Liu,
*On the localization of rectangular partial sums for multiple Fourier series*, Proc. Amer. Math. Soc.**34**(1972), 90–96. MR**294993**, DOI 10.1090/S0002-9939-1972-0294993-6 - D. Russell Luke, James V. Burke, and Richard G. Lyon,
*Optical wavefront reconstruction: theory and numerical methods*, SIAM Rev.**44**(2002), no. 2, 169–224. MR**1926097**, DOI 10.1137/S003614450139075 - C. L. Mallows and J. M. C. Clark,
*Linear-intercept distributions do not characterize plane sets*, J. Appl. Probability**7**(1970), 240–244. MR**259976**, DOI 10.2307/3212164 - G. Matheron,
*Random sets and integral geometry*, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, New York-London-Sydney, 1975. With a foreword by Geoffrey S. Watson. MR**0385969** - G. Matheron,
*La formule de Steiner pour les érosions*, J. Appl. Probability**15**(1978), no. 1, 126–135 (French). MR**493914**, DOI 10.2307/3213242 - G. Matheron, Le covariogramme géometrique des compacts convexes des $R^2$,
*Technical Report N-2/86/G, Centre de Géostatistique, Ecole Nationale Supérieure des Mines de Paris*, 1986. - Amyn Poonawala, Peyman Milanfar, and Richard J. Gardner,
*Shape estimation from support and diameter functions*, J. Math. Imaging Vision**24**(2006), no. 2, 229–244. MR**2227098**, DOI 10.1007/s10851-005-3625-z - Joseph Rosenblatt,
*Phase retrieval*, Comm. Math. Phys.**95**(1984), no. 3, 317–343. MR**765273** - Michel Schmitt,
*On two inverse problems in mathematical morphology*, Mathematical morphology in image processing, Opt. Engrg., vol. 34, Dekker, New York, 1993, pp. 151–169. MR**1196706** - M. Schmuckenschläger,
*The distribution function of the convolution square of a convex symmetric body in $\textbf {R}^n$*, Israel J. Math.**78**(1992), no. 2-3, 309–334. MR**1194970**, DOI 10.1007/BF02808061 - J. Serra,
*Image analysis and mathematical morphology*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1984. English version revised by Noel Cressie. MR**753649** - Rolf Schneider,
*Convex bodies: the Brunn-Minkowski theory*, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR**1216521**, DOI 10.1017/CBO9780511526282 - Antonis Tsolomitis,
*Convolution bodies and their limiting behavior*, Duke Math. J.**87**(1997), no. 1, 181–203. MR**1440068**, DOI 10.1215/S0012-7094-97-08708-1 - Sara A. van de Geer,
*Applications of empirical process theory*, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 6, Cambridge University Press, Cambridge, 2000. MR**1739079** - Aad W. van der Vaart and Jon A. Wellner,
*Weak convergence and empirical processes*, Springer Series in Statistics, Springer-Verlag, New York, 1996. With applications to statistics. MR**1385671**, DOI 10.1007/978-1-4757-2545-2 - Elisabeth Werner,
*A general geometric construction for affine surface area*, Studia Math.**132**(1999), no. 3, 227–238. MR**1669674**, DOI 10.4064/sm-132-3-227-238

## Additional Information

**Gabriele Bianchi**- Affiliation: Dipartimento di Matematica, Università di Firenze, Viale Morgagni 67/A, Firenze, Italy I-50134
- MR Author ID: 239050
- Email: gabriele.bianchi@unifi.it
**Richard J. Gardner**- Affiliation: Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063
- MR Author ID: 195745
- Email: Richard.Gardner@wwu.edu
**Markus Kiderlen**- Affiliation: Department of Mathematical Sciences, University of Aarhus, Ny Munkegade, DK–8000 Aarhus C, Denmark
- Email: kiderlen@imf.au.dk
- Received by editor(s): July 7, 2009
- Received by editor(s) in revised form: June 30, 2010, and July 23, 2010
- Published electronically: October 5, 2010
- Additional Notes: The second author was supported in part by U.S. National Science Foundation grant DMS-0603307.
- © Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**24**(2011), 293-343 - MSC (2010): Primary 42--04, 42B10, 52--04, 52A20; Secondary 52B11, 62H35
- DOI: https://doi.org/10.1090/S0894-0347-2010-00683-2
- MathSciNet review: 2748395