Optimal quantized compressed sensing, one-bit phase retrieval, and two-bit covariance estimation

Abstract

This thesis focuses on signal reconstruction and statistical estimation under quantization. We develop efficient and optimal algorithms for three problems: quantized compressed sensing, one-bit phase retrieval and two-bit covariance estimation.

Quantized compressed sensing studies the reconstruction of structured signals from quantized linear measurements. Although this is a well-developed area, an efficient and optimal algorithm for recovering sparse x from sign(Ax) was proved very recently by Matsumoto and Mazumdar. In Chapter 2 we substantially generalize their work by showing that projected gradient descent is optimal in recovering generally structured signals living in a star-shaped set from general quantized observations.

In spite of some studies of one-bit phase retrieval in the literature, little was known about the theoretical aspect. In Chapter 3, we provide clear understanding on the optimal error rates and efficient algorithms about one-bit phase retrieval. Intriguingly, these results find the phaseless counterparts of the major findings in one-bit compressed sensing theory.

Covariance estimation is a fundamental statistical estimation problem, while the study of two-bit covariance that only relies on two bits per entry from the sample was recently commenced by Dirksen, Maly and Rauhut. Their estimator for sub-Gaussian samples is sub-optimal when the diagonal of the underlying covariance is dominated by a few entries. In Chapter 4, we develop the first near-optimal 2-bit covariance estimator with almost dimension-free error rate in operator norm. This is built upon the idea of using coordinate-dependent dithering scales.