TY - JOUR

T1 - Phase retrieval without small-ball probability assumptions

AU - Krahmer, Felix

AU - Liu, Yi Kai

N1 - Publisher Copyright:
© 2017 IEEE.

PY - 2018/1

Y1 - 2018/1

N2 - In the context of the phase retrieval problem, it is known that certain natural classes of measurements, such as Fourier measurements and random Bernoulli measurements, do not lead to the unique reconstruction of all possible signals, even in combination with certain practically feasible random masks. To avoid this difficulty, the analysis is often restricted to measurement ensembles (or masks) that satisfy a small-ball probability condition, in order to ensure that the reconstruction is unique. This paper shows a complementary result: for random Bernoulli measurements, there is still a large class of signals that can be reconstructed uniquely, namely, those signals that are non-peaky. In fact, this result is much more general: it holds for random measurements sampled from any subgaussian distribution D, without any small-ball conditions. This is demonstrated in two ways: 1) a proof of stability and uniqueness and 2) a uniform recovery guarantee for the PhaseLift algorithm. In all of these cases, the number of measurements m approaches the information-theoretic lower bound. Finally, for random Bernoulli measurements with erasures, it is shown that PhaseLift achieves uniform recovery of all signals (including peaky ones).

AB - In the context of the phase retrieval problem, it is known that certain natural classes of measurements, such as Fourier measurements and random Bernoulli measurements, do not lead to the unique reconstruction of all possible signals, even in combination with certain practically feasible random masks. To avoid this difficulty, the analysis is often restricted to measurement ensembles (or masks) that satisfy a small-ball probability condition, in order to ensure that the reconstruction is unique. This paper shows a complementary result: for random Bernoulli measurements, there is still a large class of signals that can be reconstructed uniquely, namely, those signals that are non-peaky. In fact, this result is much more general: it holds for random measurements sampled from any subgaussian distribution D, without any small-ball conditions. This is demonstrated in two ways: 1) a proof of stability and uniqueness and 2) a uniform recovery guarantee for the PhaseLift algorithm. In all of these cases, the number of measurements m approaches the information-theoretic lower bound. Finally, for random Bernoulli measurements with erasures, it is shown that PhaseLift achieves uniform recovery of all signals (including peaky ones).

KW - Convex optimization

KW - Inverse problems

KW - Phase retrieval

KW - PhaseLift

KW - Random measurements

KW - Reconstruction algorithms

KW - Sampling methods

UR - http://www.scopus.com/inward/record.url?scp=85030780717&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2757520

DO - 10.1109/TIT.2017.2757520

M3 - Article

AN - SCOPUS:85030780717

SN - 0018-9448

VL - 64

SP - 485

EP - 500

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 1

ER -