Geometry of second moments : recovery estimates for moment inversion problems.

Abstract

The goal of this thesis is to consider two instances of a class of reconstruction problems that aim to recover an unknown signal x from indirect measurements m(x) that are algebraic in nature. Such problems are paramount in mathematics, enjoying applications in a wide array of fields like molecular imaging, machine learning, computer vision, distance geometry and geopositioning. In particular, we study the generic crystallographic phase retrieval problem and establish prior conditions on the signal x ∈ Rn (and Cn) that guarantee its recovery from its power spectrum measurements. Subsequently, we study the orthogonal beltway problem and prove a result that characterizes the recoverability of a discretely supported binary signal x from the knowledge of the unlabeled set of inner products ⟨vi, vj⟩ of its support, settling the conjecture made in [21]. We also utilize this result and its connections to Euclidean distance geometry to develop a polynomial-time algorithm that recovers the support set of x and is robust to small amounts of noise, thereby making incremental progress towards the noisy variant of the unlabeled distance geometry problem which remains largely open. We resolve both of the the central problems of this thesis by recasting them as special instances of the problem of recovering an unknown signal from its (noiseless) second moment under the multi-reference alignment (MRA) model, for which a rich theory has been developed in [18].