Algorithms and error bounds for noisy phase retrieval with low-redundancy frames

The main objective of this paper is to find algorithms accompanied by explicit error bounds for phase retrieval from noisy magnitudes of frame coefficients when the underlying frame has a low redundancy. We achieve these goals with frames consisting of N=6d−3 vectors spanning a d-dimensional complex Hilbert space. The two algorithms we use, phase propagation or the kernel method, are polynomial time in the dimension d. To ensure a successful approximate recovery, we assume that the noise is sufficiently small compared to the squared norm of the vector to be recovered. In this regime, we derive an explicit error bound that is inverse proportional to the signal-to-noise ratio, with a constant of proportionality that depends only on the dimension d. Properties of the reproducing kernel space of complex polynomials and of trigonometric polynomials are central in our error estimates.