Phase Retrieval from Random One-Bit Measurements

Phase retrieval in real or complex Hilbert spaces is the task of recovering a vector, up to an overall unimodular multiplicative constant, from norms of projections onto subspaces. This dissertation deals with phase retrieval of normalized vectors after the norms of projections are quantized by pairwise comparison to retain only one bit of information. In more specific, geometric terms, we choose a sequence of pairs of subspaces in a real or complex Hilbert space and only record which subspace from each pair is closer to the input vector. The main goal of this paper is to find a feasible algorithm for approximate recovery based on the qualitative information gained about the vector from these binary questions, and to establish error bounds for the approximate recovery procedure. The recovery algorithm we define uses the qualitative proximity information encoded in the binary measurement of an input vector to assemble an auxiliary matrix, and then chooses a unit vector in the principal eigenspace of this auxiliary matrix as the estimate for the input vector. For this measurement and recovery procedure, we provide a pointwise bound for fixed input vectors and a uniform bound that controls the worst-case scenario among all inputs. Both bounds hold with high probability with respect to a choice of subspaces from the uniform distribution induced by the action of the orthogonal or unitary group. For real or complex vectors of dimension $n$, the pointwise bound requires $m\ge C\delta -2n\log (n)$ and the uniform bound $m\ge C\delta -2n2\log (\delta -1n)$ binary questions in order to achieve a reconstruction accuracy of $\delta$. The accuracy $\delta$ is measured by the operator norm of the difference between the rank-one orthogonal projections corresponding to the normalized input vector and its approximate recovery. After establishing the pointwise and uniform error bounds for noiseless binary measurements, we consider the case of noisy measurements. Noise for a binary-valued measurement takes the form of bit-flips that corrupt the proximity information encoded in the binary measurement. We show that our measurement and recovery scheme is robust in the presence of a percentage of adversarial bit-flips on the order of $1n$. We also consider random bit-flips and show in this setting that the mean squared error of reconstruction decays with respect to the number of projections $m$ on the order of $\log (m)m$.