Binary Discrete Fourier Transform and Its Inversion

A binary vector has elements that are either 0 or 1. We investigate whether and how a binary vector of known length N can be reconstructed from a limited set of its discrete Fourier transform (DFT) coefficients. A priori information that the vector is binary provides a powerful constraint. We prove that a binary vector is uniquely defined by its first two DFT coefficients (zeroth, which gives the popcount, and first) if N is prime. If N has two prime factors, additional DFT coefficients must be included in the data set to guarantee uniqueness, and we find the number of required coefficients in this case theoretically. In the presence of noise, one may need to know even more DFT coefficients to guarantee stable and unique inverse solution. Our results indicate that stable inversion can be obtained when the number of known coefficients is about $1/3$ of the total. This entails the effect of super-resolution (the resolution limit is improved by the factor of ~ 3). Two algorithms for solving the inverse problem numerically are proposed and tested. The first algorithm is combinatorial and suitable for problems with N ≲60. Although the problem in general is NP-hard, the required computational complexity in a typical application of the algorithm is much smaller than that of exhaustive search. The second algorithm is based on optimization of a non-convex continuous functional with algebraic computational complexity. This latter method is applicable to much larger values of N, as we demonstrate numerically for N=199.