Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



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

Authors: Gabriele Bianchi, Richard J. Gardner and Markus Kiderlen
Journal: J. Amer. Math. Soc. 24 (2011), 293-343
MSC (2010): Primary 42B10, 52A20; Secondary 52B11, 62H35
Published electronically: October 5, 2010
MathSciNet review: 2748395
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. R. J. Adler and R. Pyke, Problem 91-3, Inst. Math. Statist. Bull. 20 (1991), 409.
  • 2. R. J. Adler and R. Pyke, Scanning Brownian processes, Adv. in Appl. Probab. 39 (2007), 613-629. MR 1450931 (98e:60054)
  • 3. I. A. Ahmad and P.-E. Lin, Fitting a multiple regression function, J. Statist. Plann. Inference 9 (1984), 163-176. MR 738366 (86a:62053)
  • 4. G. Averkov and G. Bianchi, Confirmation of Matheron's conjecture on the covariogram of a planar convex body, J. Europ. Math. Soc. 11 (2009), 1187-1202. MR 2557133
  • 5. M. Baake and U. Grimm, Homometric model sets and window covariograms, Z. Krist. 222 (2007), 54-58.
  • 6. C. Benassi and G. D'Ercole, An algorithm for reconstructing a convex polygon from its covariogram, Rend. Istit. Mat. Univ. Trieste 39 (2007), 457-476. MR 2441634 (2009e:52004)
  • 7. G. Bianchi, Matheron's conjecture for the covariogram problem, J. London Math. Soc. (2) 71 (2005), 203-220. MR 2108257 (2005i:60021)
  • 8. G. Bianchi, The covariogram determines three-dimensional convex polytopes, Adv. Math. 220 (2009), 1771-1808. MR 2493181 (2010i:60035)
  • 9. G. Bianchi, F. Segala, and A. Volčič, The solution of the covariogram problem for plane $ {\mathcal{C}}^2_+$ convex bodies, J. Differential Geom. 60 (2002), 177-198. MR 1938112 (2003h:52001)
  • 10. P. Billingsley, Convergence of Probability Measures, second edition, John Wiley and Sons, New York, 1999. MR 1700749 (2000e:60008)
  • 11. J. Bourgain and J. Lindenstrauss, Projection bodies, in: Geometric Aspects of Functional Analysis (1986/7), Lecture Notes in Math. 1317, Springer, Berlin, 1988, pp. 250-270. MR 950986 (89g:46024)
  • 12. L. Brandolini, S. Hoffman, and A. Iosevich, Sharp rate of average decay of the Fourier transform of a bounded set, Geom. Funct. Anal. 13 (2003), 671-680. MR 2006553 (2004g:42015)
  • 13. N. S. Brannen, The Wills conjecture, Trans. Amer. Math. Soc. 349 (1997), 3977-3987. MR 1373630 (97m:52024)
  • 14. V. V. Buldygin and Y. V. Kozachenko, Metric Characterization of Random Variables and Random Processes, American Mathematical Society, Providence, RI, 2000. MR 1743716 (2001g:60089)
  • 15. A. Cabo and A. Baddeley, Estimation of mean particle volume using the set covariance function, Adv. in Appl. Probab. 35 (2003), 27-46. MR 1974301 (2004c:60025)
  • 16. S. 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 (89m:52002)
  • 17. R. M. Dudley, Distances of probability measures and random variables, Ann. Math. Stat. 39 (1968), 1563-1572. MR 0230338 (37:5900)
  • 18. J. R. Fienup, Phase retrieval algorithms: a comparison, Appl. Opt. 21 (1982), 2758-2769.
  • 19. B. Galerne, Computation of the perimeter of measurable sets via their covariogram. Applications to random sets, Image Anal. Stereol., to appear.
  • 20. R. J. Gardner, Geometric Tomography, second edition, Cambridge University Press, New York, 2006. MR 2251886 (2007i:52010)
  • 21. R. J. Gardner, The Brunn-Minkowski inequality, Bull. Amer. Math. Soc. 39 (2002), 355-405. MR 1898210 (2003f:26035)
  • 22. R. J. Gardner, P. Gronchi, and C. Zong, Sums, projections, and sections of lattice sets, and the discrete covariogram, Discrete Comput. Geom. 34 (2005), 391-409. MR 2160045 (2006i:52026)
  • 23. R. J. Gardner and M. Kiderlen, A solution to Hammer's X-ray reconstruction problem, Adv. Math. 214 (2007), 323-343. MR 2348033 (2008h:52004)
  • 24. R. J. Gardner, M. Kiderlen, and P. Milanfar, Convergence of algorithms for reconstructing convex bodies and directional measures, Ann. Statist. 34 (2006), 1331-1374. MR 2278360 (2008e:68146)
  • 25. R. J. Gardner and P. Milanfar, Reconstruction of convex bodies from brightness functions, Discrete Comput. Geom. 29 (2003), 279-303. MR 1957233 (2004a:68145)
  • 26. R. J. Gardner and G. Zhang, Affine inequalities and radial mean bodies, Amer. J. Math. 120 (1998), 493-504. MR 1623396 (99e:52006)
  • 27. P. Goodey, R. Schneider, and W. Weil, On the determination of convex bodies by projection functions, Bull. London Math. Soc. 29 (1997), 82-88. MR 1416411 (97g:52017)
  • 28. A. Guntuboyina, Lower bounds for the minimax risk using $ f$-divergences and applications, IEEE Trans. Inform. Theory, to appear.
  • 29. J. Hoffmann-Jørgensen, Probability With a View Toward Statistics, Vol. I, Chapman & Hall, New York, 1994. MR 1278485 (95c:60001a)
  • 30. T.-C. 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), 153-162. MR 1015785 (91f:60061)
  • 31. D. Hug and R. Schneider, Stability results involving surface area measures of convex bodies, Rend. Circ. Mat. Palermo (2) Suppl. No. 70, part II (2002), 21-51. MR 1962583 (2004b:52004)
  • 32. N. E. Hurt, Phase Retrieval and Zero Crossings, Kluwer, Dordrecht, 1989. MR 1093464 (92k:94002)
  • 33. M. Kiderlen and E. B. V. Jensen, Estimation of the directional measure of planar random sets by digitization, Adv. Appl. Probab. 35 (2003), 583-602. MR 1990605 (2004k:60023)
  • 34. M. V. Klibanov, P. E. Sacks, and A. V. Tikhonravov, The phase retrieval problem, Inverse Problems 11 (1995), 1-28. MR 1313598 (95m:35203)
  • 35. F. C. Liu, On the localization of rectangular partial sums for multiple Fourier series, Proc. Amer. Math. Soc. 34 (1972), 90-96. MR 0294993 (45:4061)
  • 36. D. R. Luke, J. V. Burke, and R. G. Lyon, Optical wavefront reconstruction: theory and numerical methods, SIAM Rev. 44 (2002), 169-224. MR 1926097 (2003i:78006)
  • 37. C. L. Mallows and J. M. C. Clark, Linear-intercept distributions do not characterize plane sets, J. Appl. Probab. 7 (1970), 240-244. MR 0259976 (41:4605)
  • 38. G. Matheron, Random Sets and Integral Geometry, Wiley, New York, 1975. MR 0385969 (52:6828)
  • 39. G. Matheron, La formule de Steiner pour les érosions, J. Appl. Probab. 15 (1978), 126-135. MR 0493914 (58:12874)
  • 40. 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.
  • 41. A. Poonawala, P. Milanfar, and R. J. Gardner, Shape estimation from support and diameter functions, J. Math. Imaging Vision 24 (2006), 229-244. MR 2227098 (2007j:94009)
  • 42. J. Rosenblatt, Phase retrieval, Commun. Math. Phys. 95 (1984), 317-343. MR 765273 (86k:82075)
  • 43. M. Schmitt, On two inverse problems in mathematical morphology, in: Mathematical Morphology in Image Processing, ed. by E. R. Dougherty, Marcel Dekker, New York, pp. 151-169. MR 1196706 (93j:68223)
  • 44. M. Schmuckenschläger, The distribution function of the convolution square of a convex symmetric body in $ \mathbb{R}^n$, Israel J. Math. 78 (1992), 309-334. MR 1194970 (93k:52008)
  • 45. J. Serra, Image Analysis and Mathematical Morphology, Academic Press, London, 1982. MR 753649 (87d:68106)
  • 46. R. Schneider, Convex Bodies: The Brunn-Minkowski Theory, Cambridge University Press, Cambridge, 1993. MR 1216521 (94d:52007)
  • 47. A. Tsolomitis, Convolution bodies and their limiting behavior, Duke Math. J. 87 (1997), 181-203. MR 1440068 (98c:52007)
  • 48. S. van de Geer, Applications of Empirical Process Theory, Cambridge University Press, New York, 2000. MR 1739079 (2001h:62002)
  • 49. A. W. van der Waart and J. A. Wellner, Weak Convergence and Empirical Processes, Springer, New York, 1996. MR 1385671 (97g:60035)
  • 50. E. Werner, A general geometric construction for affine surface area, Studia Math. 132 (1999), 227-238. MR 1669674 (99m:52008)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 42B10, 52A20, 52B11, 62H35

Retrieve articles in all journals with MSC (2010): 42B10, 52A20, 52B11, 62H35

Additional Information

Gabriele Bianchi
Affiliation: Dipartimento di Matematica, Università di Firenze, Viale Morgagni 67/A, Firenze, Italy I-50134

Richard J. Gardner
Affiliation: Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063

Markus Kiderlen
Affiliation: Department of Mathematical Sciences, University of Aarhus, Ny Munkegade, DK–8000 Aarhus C, Denmark

Keywords: Algorithm, autocorrelation, convex body, convex polytope, covariogram, geometric tomography, image analysis, least squares, phase retrieval, quasicrystal, set covariance
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.
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society