论文标题
二元离散傅立叶变换及其反转
Binary Discrete Fourier Transform and its Inversion
论文作者
论文摘要
长度$ n $的二进制向量的元素为0或1。我们研究了是否以及如何从有限的离散傅立叶变换（DFT）系数中重建已知长度的二元向量。向量为二进制的先验信息提供了强大的约束。我们证明，如果$ n $是PRIME，则二进制向量是由其两个复杂的DFT系数（Zeroth，Zeroth提供的）唯一定义的。如果$ n $有两个主要因素，则必须在数据集中包含其他DFT系数，以确保唯一性，并且从理论上讲，我们发现所需系数的数量。一个人可能需要了解更多的DFT系数，以确保反转的稳定性。但是，我们的结果表明，当已知系数的数量约为总计$ 1/3 $时，可以获得稳定的反转。这需要超级分辨率的效果（分辨率限制提高了$ \ sim 3 $）。
A binary vector of length $N$ has elements that are either 0 or 1. We investigate the question of whether and how a binary vector of known length 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 two complex 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 theoretically. One may need to know even more DFT coefficients to guarantee stability of inversion. However, 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 $\sim 3$).
