High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization
This addresses the problem of efficient data compression and estimation in high-dimensional statistics for applications like signal processing and machine learning, representing a novel extension to heavy-tailed data and robust settings.
The paper tackles high-dimensional statistical estimation using a uniformly dithered 1-bit quantization scheme, applying it to sparse covariance matrix estimation, sparse linear regression, and matrix completion. In the sub-Gaussian regime, the estimators achieve near minimax rates, while in the heavy-tailed regime, they provide first or improved results with almost tight rates in some cases.
In this paper, we propose a uniformly dithered 1-bit quantization scheme for high-dimensional statistical estimation. The scheme contains truncation, dithering, and quantization as typical steps. As canonical examples, the quantization scheme is applied to the estimation problems of sparse covariance matrix estimation, sparse linear regression (i.e., compressed sensing), and matrix completion. We study both sub-Gaussian and heavy-tailed regimes, where the underlying distribution of heavy-tailed data is assumed to have bounded moments of some order. We propose new estimators based on 1-bit quantized data. In sub-Gaussian regime, our estimators achieve near minimax rates, indicating that our quantization scheme costs very little. In heavy-tailed regime, while the rates of our estimators become essentially slower, these results are either the first ones in an 1-bit quantized and heavy-tailed setting, or already improve on existing comparable results from some respect. Under the observations in our setting, the rates are almost tight in compressed sensing and matrix completion. Our 1-bit compressed sensing results feature general sensing vector that is sub-Gaussian or even heavy-tailed. We also first investigate a novel setting where both the covariate and response are quantized. In addition, our approach to 1-bit matrix completion does not rely on likelihood and represent the first method robust to pre-quantization noise with unknown distribution. Experimental results on synthetic data are presented to support our theoretical analysis.