Spherical designs as a tool for derandomization: The case of PhaseLift

The problem of retrieving phase information from amplitude measurements alone has appeared in many scientific disciplines over the last century. PhaseLift is a recently introduced algorithm for phase recovery that is computationally tractable and numerically stable. However, initial rigorous performance guarantees relied specifically on Gaussian random measurement vectors. To date, it remains unclear which properties of the measurements render the problem well-posed. With this question in mind, we employ the concept of spherical t-designs to achieve a partial derandomziation of PhaseLift. Spherical designs are ensembles of vectors which reproduce the first 2t moments of the uniform distribution on the complex unit sphere. As such, they provide notions of 'evenly distributed' sets of vectors, ranging from tight frames (t = 1) to the full sphere, as t approaches infinity. Beyond the specific case of PhaseLift, this result highlights the utility of spherical designs for the derandomization of data recovery schemes.