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 42--04, 42B10, 52--04, 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?)


Similar Articles

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

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

Additional Information

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

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

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.