Total: 1
In this paper, we study the sample complexity and develop efficient optimal algorithms for 1-bit phase retrieval: recovering a signal x∈Rn from m phaseless bits {sign(|a⊤ix|−τ)}mi=1 generated by standard Gaussian ais. By investigating a phaseless version of random hyperplane tessellation, we show that (constrained) hamming distance minimization uniformly recovers all unstructured signals with Euclidean norm bounded away from zero and infinity to the error O((n/m)log(m/n)), and O((k/m)log(mn/k2)) when restricting to k-sparse signals. Both error rates are shown to be information-theoretically optimal, up to a logarithmic factor. Intriguingly, the optimal rate for sparse recovery matches that of 1-bit compressed sensing, suggesting that the phase information is non-essential for 1-bit compressed sensing. We also develop efficient algorithms for 1-bit (sparse) phase retrieval that can achieve these error rates. Specifically, we prove that (thresholded) gradient descent with respect to the one-sided ℓ1-loss, when initialized via spectral methods, converges linearly and attains the near optimal reconstruction error, with sample complexity O(n) for unstructured signals and O(k2log(n)log2(m/k)) for k-sparse signals. Our proof is based upon the observation that a certain local (restricted) approximate invertibility condition is respected by Gaussian measurements.