No existence of linear algorithm for Fourier phase retrieval

09/13/2022
by   Meng Huang, et al.
0

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 𝐱∈ℂ^N in (N) log(1/ϵ) time to reach ϵ-precision from its magnitude of discrete Fourier transform and its initial value x(0), then 𝒫=𝒩𝒫. 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset