Binary Signal Perfect Recovery from partial DFT coefficients

How to perfectly recover a binary signal from the partial Discrete Fourier transform (DFT) coefficients is studied. The theoretic lower bound is derived and a practical recovery strategy is developed. The concept of ambiguity pair is introduced and used to prove that when the signal length is $N$, then at least $\tau(N)$ DFT points must be sampled, where $\tau(N)$ is the total number of positive divisors of length $N$. A recovery algorithm is also proposed and implemented. In our result, we can sample 11\% of the total DFT coefficients to perfectly recover the binary signal. We also extend our result to two-dimensional cases.