Algorithms and error bounds for noisy phase retrieval with low-redundancy frames
It provides the first explicit error bounds for phase retrieval with low-redundancy frames, addressing a gap in theoretical guarantees for practical applications.
This paper develops polynomial-time algorithms for phase retrieval from noisy magnitude measurements using low-redundancy frames with N=6d-3 vectors, achieving error bounds inversely proportional to the signal-to-noise ratio under small noise assumptions.
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, the error bound is inverse proportional to the signal-to-noise ratio. Upper and lower bounds on the sample values of trigonometric polynomials are a central technique in our error estimates.