2022/09/13 by Meng Huang, Huang, Meng, Zhiqiang Xu +1
Engineering · Physics and Astronomy · #Adaptive optics and wavefront sensing #Advanced Measurement and Metrology Techniques #Advanced X-ray Imaging Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Retrieval (cs.IR) #Information Theory (cs.IT) #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.2209.05673
openalex publication_date 2022/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fourier phase retrieval, which seeks to reconstruct a signal from its Fourier magnitude, is of fundamental importance in fields of engineering and science. In this paper, we give a theoretical understanding of algorithms for Fourier phase retrieval. Particularly, we show if there exists an algorithm which could reconstruct an arbitrary signal \mathbf x∈ \mathbb 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 demystifies the phenomenon that, although almost all signals are determined uniquely by their Fourier magnitude with a prior conditions, there is no algorithm with theoretical guarantees being proposed over the past few decades. Our proofs employ the result in computational complexity theory that Product Partition problem is NP-complete in the strong sense.