Recovery of Integer Images from Minimal DFT Measurements: Uniqueness and Inversion Algorithms
For image reconstruction tasks where integer constraints apply, this work provides theoretical guarantees and practical algorithms for recovery from undersampled DFT measurements.
This paper shows that integer-valued images can be uniquely recovered from a minimal subset of DFT coefficients, using a reduction to 1D problems and dynamic programming with lattice-based algorithms. The method drastically reduces search space compared to brute force.
Exact reconstruction of an image from measurements of its Discrete Fourier Transform (DFT) typically requires all DFT coefficients to be available. However, incorporating the prior assumption that the image contains only integer values enables unique recovery from a limited subset of DFT coefficients. This paper develops both theoretical and algorithmic foundations for this problem. We use algebraic properties of the DFT to define a reduction from two-dimensional recovery to several well-chosen one-dimensional recoveries. Our reduction framework characterizes the minimum number and location of DFT coefficients that must be sampled to guarantee unique reconstruction of an integer-valued image. Algorithmically, we develop reconstruction procedures which use dynamic programming to efficiently recover an integer signal or image from its minimal set of DFT measurements. While the new inversion algorithms still involve NP-hard subproblems, we demonstrate how the divide-and-conquer approach drastically reduces the associated search space. To solve the NP-hard subproblems, we employ a lattice-based framework which leverages the LLL approximation algorithm to make the algorithms fast and practical.