A Partial Derandomization of Phase Retrieval via PhaseLift
Felix Krahmer
Gottingen
Abstract:
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 efficient, numerically
stable, and comes with rigorous performance guarantees. PhaseLift is
optimal in the sense that the number of amplitude measurements
required for phase reconstruction scales linearly with the dimension
of the signal. However, it specifically demands Gaussian random
measurement vectors - a limitation that restricts practical utility
and obscures the specific properties of measurement ensembles that
enable phase retrieval. Here we present a partial derandomization of
PhaseLift that only requires sampling from certain polynomial size
vector configurations, called t-designs. Such configurations have
been studied in algebraic combinatorics, coding theory, and quantum
information. We prove reconstruction guarantees for a number of
measurements that depends on the degree t of the design. If the
degree is allowed to to grow logarithmically with the dimension, the
bounds become tight up to polylog-factors. Beyond the specific case
of PhaseLift, this work highlights the utility of spherical designs
for the derandomization of data recovery schemes.