Phase retrieval: Stability and recovery guarantees

We consider stability and uniqueness in real phase retrieval problems over general input sets, when the data consists of random and noisy quadratic measurements of an unknown input x₀εRⁿ that lies in a general set T. We study conditions under which x₀ can be stably recovered from the measurements. In the noise-free setting we show that the number of measurements needed to ensure a unique and stable solution depends on the set T through its Gaussian mean-width, which can be computed explicitly for many sets of interest. In particular, for k-sparse inputs, O(klog(n/k)) measurements suffice, while if x₀ is an arbitrary vector in R ⁿ, O(n) measurements are sufficient. In the noisy case, we show that if the empirical risk is bounded by a given, computable constant that depends only on statistical properties of the noise, the error with respect to the true input is bounded by the same Gaussian parameter (up to logarithmic factors). Therefore, the number of measurements required for stable recovery is the same as in the noise-free setting up to log factors. It turns out that the complexity parameter for the quadratic problem is the same as the one used for analyzing stability in linear measurements under very general conditions. Thus, no substantial price has to be paid in terms of stability when there is no knowledge of the phase of the measurements.