No existence of a linear algorithm for the one-dimensional Fourier phase retrieval

Fourier phase retrieval, which aims to reconstruct a signal from its Fourier magnitude, is of fundamental importance in fields of engineering and science. In this paper, we provide a theoretical understanding of algorithms for the one-dimensional Fourier phase retrieval problem. Specifically, we demonstrate that if an algorithm exists which can reconstruct an arbitrary signal x∈CN in Poly(N)log⁡(1/ϵ) time to reach ϵ-precision from its magnitude of discrete Fourier transform and its initial value x(0), then P=NP. This partially elucidates the phenomenon that, despite the fact that almost all signals are uniquely determined by their Fourier magnitude and the absolute value of their initial value |x(0)|, no algorithm with theoretical guarantees has been proposed in the last few decades. Our proofs employ the result in computational complexity theory that the Product Partition problem is NP-complete in the strong sense.