The Local Landscape of Phase Retrieval Under Limited Samples

Abstract

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(d 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: ^d: o_d(1) \|w-w^*\| 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 o_d(1)-loss solution exponentially fast. Furthermore, we show that when n=o(d d), there is a radius of (1/d) 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.

Tasks

Reproductions