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 2), 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).

VL - 64 U4 - 485-500 UR - http://ieeexplore.ieee.org/document/8052535/ CP - 1 U5 - 10.1109/TIT.2017.2757520 ER - TY - JOUR T1 - Phase Retrieval Without Small-Ball Probability Assumptions: Stability and Uniqueness JF - SampTA Y1 - 2015 A1 - Felix Krahmer A1 - Yi-Kai Liu AB - We study stability and uniqueness for the phase retrieval problem. That is, we ask when is a signal x ∈ R n stably and uniquely determined (up to small perturbations), when one performs phaseless measurements of the form yi = |a T i x| 2 (for i = 1, . . . , N), where the vectors ai ∈ R n are chosen independently at random, with each coordinate aij ∈ R being chosen independently from a fixed sub-Gaussian distribution D. It is well known that for many common choices of D, certain ambiguities can arise that prevent x from being uniquely determined. In this note we show that for any sub-Gaussian distribution D, with no additional assumptions, most vectors x cannot lead to such ambiguities. More precisely, we show stability and uniqueness for all sets of vectors T ⊂ R n which are not too peaky, in the sense that at most a constant fraction of their mass is concentrated on any one coordinate. The number of measurements needed to recover x ∈ T depends on the complexity of T in a natural way, extending previous results of Eldar and Mendelson [12]. U4 - 411-414 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7148923&tag=1 ER -