Sampling complexity on phase retrieval from masked Fourier measurements via Wirtinger flow*This work is supported by the key project of NSFC of China under grant numbers U21A20426 and NSFC ofChina under grant number 12101170, 12071426, 11901143, 11971427 and the Zhejiang Provincial Natural Science Foundation of China under grant number LQ19A010008. (1st October 2022) - Li, Huiping; Li, Song; Xia, Yu
Abstract: In this paper, we consider the problem of phase retrieval under masked Fourier measurements. Specifically, we focus on a question raised by E Candès et al, namely, to reduce the sampling complexity of such problem in noiseless case. We provide a truncated Wirtinger flow (TWF) algorithm with resampling to solve the problem. This algorithm starts with an initial guess computed by some truncated spectral method, then proceeds by successively refining the estimation via an update rule that bears a strong resemblance to a gradient descent scheme. These careful selection rules provide better initial guess and descent direction. We prove that when the sampling complexity is O ( n log n ), we get some good initial solution. Furthermore, the sequence generated by the resampled TWF algorithm can linearly converge to the true signal x ∈ C n with ϵ -accuracy up to a global phase, provided with the sampling complexity O ( log ( 1 ϵ ) n log 2 ⁡ n ) . To some degree, we improve the results proposed by E Candès et al, which demand O ( n log 4 n ) samples.