The Local Landscape of Phase Retrieval Under Limited Samples

In this paper, we present a fine-grained analysis of the local landscape of phase retrieval under the regime of limited samples. Specifically, we aim to ascertain the minimal sample size required to guarantee a benign local landscape surrounding global minima in high dimensions. Let n and d denote the sample size and input dimension, respectively. We first explore the local convexity and establish that when n=o(dlog d), for almost every fixed point in the local ball, the Hessian matrix has negative eigenvalues, provided d is sufficiently large. % Consequently, the local landscape is highly non-convex. We next consider the one-point convexity and show that, as long as n=ω(d), with high probability, the landscape is one-point strongly convex in the local annulus: w∈ℝd: od(1)leqslant |w-w^*|leqslant c, where w^* is the ground truth and c is an absolute constant. This implies that gradient descent, initialized from any point in this domain, can converge to an od(1)-loss solution exponentially fast. Furthermore, we show that when n=o(dlog d), there is a radius of widetildeThetaleft(√1/dright) such that one-point convexity breaks down in the corresponding smaller local ball. This indicates an impossibility of establishing a convergence to the exact w^* for gradient descent under limited samples by relying solely on one-point convexity.