Reconstructing Rational Functions on Finite Abelian Groups with Higher Autocorrelations

Abstract

The higher-order autocorrelations of integer-valued or rational-valued functions on finite Abelian groups appear naturally in X-ray crystallography, and have applications in computer vision systems, correlation tomography, correlation spectroscopy, and pattern recognition. In this paper, we consider the problem of reconstructing a rational-valued function on finite Abelian groups from its higher-order autocorrelations. We describe an explicit reconstruction algorithm, and prove that the autocorrelations up to order $3r+3$ are always sufficient to determine the data up to translation, where $r$ is the rank of the group. We also provide examples of rational-valued functions on finite Abelian group which are not determined by their autocorrelations up to order $3r+2$. In particular, we provide a sharp upper bound on the separating degree of the regular representation of a finite Abelian group in terms of its rank.

28 pages, 2 figures