Reconstructing Gridded Data from Higher Autocorrelations
This addresses a fundamental issue in fields like X-ray crystallography and computer vision, providing a theoretical guarantee for reconstruction, though it is incremental in building on existing autocorrelation methods.
The paper tackles the problem of reconstructing gridded data from its higher-order autocorrelations, proving that autocorrelations up to order 3r + 3 are sufficient for unique determination up to translation, with examples showing insufficiency at order 3r + 2.
The higher-order autocorrelations of integer-valued or rational-valued gridded data sets 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 gridded data set 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 dimension of the grid. We also provide examples of rational-valued gridded data sets which are not determined by their autocorrelations up to order 3r + 2.