Stability of reconstruction of real and complex multidimensional signals from Fourier transform magnitude

The lower bound on the condition number of the problem of reconstruction for two classes of signals is derived. The lower bound for N×N images in which the norm of the Fourier transform magnitude (FTM) vector is dominated by DC and low-frequency components is shown to grow with N. The lower bound for images in which the elements of the FTM vector contribute more or less equally to its norm is 1. The problem of reconstruction from FTM and known phase in space domain is discussed. Since the introduction of sufficiently random space-domain phase results in flattened FTM distribution, the lower bound on the condition number of the reconstruction problem with respect to the FTM vector again becomes one. This is in agreement with experimental results, indicating that randomizing the phase in space domain improves the convergence rate of the Grechberg-Saxton algorithm