Inversion of band-limited discrete Fourier transforms of binary images: Uniqueness and algorithms

Inversion of the two-dimensional discrete Fourier transform (DFT) typically requires all DFT coefficients to be known. When only band-limited DFT coefficients of a matrix are known, the original matrix can not be uniquely recovered. Using a priori information that the matrix is binary (all elements are either 0 or 1) can overcome the missing high-frequency DFT coefficients and restore uniqueness. We theoretically investigate the smallest pass band that can be applied while still guaranteeing unique recovery of an arbitrary binary matrix. The results depend on the dimensions of the matrix. Uniqueness results are proven for the dimensions $p\times q$, $p\times p$, and $p^\alpha\times p^\alpha$, where $p\neq q$ are primes numbers and $\alpha>1$ an integer. An inversion algorithm is proposed for practically recovering the unique binary matrix. This algorithm is based on integer linear programming methods and significantly outperforms naive implementations. The algorithm efficiently reconstructs $17\times17$ binary matrices using 81 out of the total 289 DFT coefficients.