In the phase retrieval problem, the goal is to recover an unknown signal vector x ∈ C~N from a small number of measurements {y_i} of the form y_i = ||~2, where m_i ∈ C~N are measurement vectors. We introduce two variations of the traditional model: the adaptive setting where measurement vectors can depend on previous measurements, and the discrete setting where each component of x is representable using a bounded number of bits. In contrast to the heavy machinery used in prior work on phase retrieval, we design simple ensembles of measurement vectors (both adaptive and deterministic) for discrete phase retrieval. The number of samples needed is significantly lower than traditional phase retrieval. Our results highlight the role of bit precision in reasoning about the sample complexity of the phase retrieval problem.
展开▼