Optimal Quantized Compressed Sensing via Projected Gradient Descent
For researchers in compressed sensing and signal processing, this work offers a unified theoretical framework that establishes optimality of PGD across various quantization models, resolving open questions about its performance.
This paper provides a unified analysis of projected gradient descent (PGD) for recovering structured signals from quantized measurements, showing that PGD achieves information-theoretic optimal rates (e.g., \( ilde{O}(k/(mL))\) for k-sparse signals) under mild conditions, matching or improving upon the sharpest known results for 1-bit and multi-bit compressed sensing.
This paper provides a unified treatment to the recovery of structured signals living in a star-shaped set from general quantized measurements $\mathcal{Q}(\mathbf{A}\mathbf{x}-\mathbfτ)$, where $\mathbf{A}$ is a sensing matrix, $\mathbfτ$ is a vector of (possibly random) quantization thresholds, and $\mathcal{Q}$ denotes an $L$-level quantizer. The ideal estimator with consistent quantized measurements is optimal in some important instances but typically infeasible to compute. To this end, we study the projected gradient descent (PGD) algorithm with respect to the one-sided $\ell_1$-loss and identify the conditions under which PGD achieves the same error rate, up to logarithmic factors. These conditions include estimates of the separation probability, small-ball probability and some moment bounds that are easy to validate. For multi-bit case, we also develop a complementary approach based on product embedding to show global convergence. When applied to popular models such as 1-bit compressed sensing with Gaussian $\mathbf{A}$ and zero $\mathbfτ$ and the dithered 1-bit/multi-bit models with sub-Gaussian $\mathbf{A}$ and uniform dither $\mathbfτ$, our unified treatment yields error rates that improve on or match the sharpest results in all instances. Particularly, PGD achieves the information-theoretic optimal rate $\tilde{O}(\frac{k}{mL})$ for recovering $k$-sparse signals, and the rate $\tilde{O}((\frac{k}{mL})^{1/3})$ for effectively sparse signals. For 1-bit compressed sensing of sparse signals, our result recovers the optimality of normalized binary iterative hard thresholding (NBIHT) that was proved very recently.