# High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization

arXiv: https://arxiv.org/abs/2202.13157 · HTML: https://mlsanity.com/paper/2202.13157/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 106 references that are in the map.
- First posted on arXiv 26 Feb 2022.

## Builds on (most cited first, 21 of 21)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Regularized estimation in sparse high-dimensional time series models](https://mlsanity.com/paper/1311.4175/) (2013)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery](https://mlsanity.com/paper/1603.08315/) (2016)
- [User-Friendly Covariance Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/1811.01520/) (2018)
- [Robust high dimensional factor models with applications to statistical machine learning](https://mlsanity.com/paper/1808.03889/) (2018)
- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [Generalized High-Dimensional Trace Regression via Nuclear Norm Regularization](https://mlsanity.com/paper/1710.08083/) (2017)
- [The Generalized Lasso for Sub-gaussian Measurements with Dithered Quantization](https://mlsanity.com/paper/1807.06976/) (2018)
- [Adaptive Multinomial Matrix Completion](https://mlsanity.com/paper/1408.6218/) (2014)
- [Deep Signal Recovery with One-Bit Quantization](https://mlsanity.com/paper/1812.00797/) (2018)
- [Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss](https://mlsanity.com/paper/2202.02063/) (2022)
- [Probabilistic low-rank matrix completion on finite alphabets](https://mlsanity.com/paper/1412.2632/) (2014)
- [Robust one-bit compressed sensing with partial circulant matrices](https://mlsanity.com/paper/1812.06719/) (2018)
- [Rate-Optimal Robust Estimation of High-Dimensional Vector Autoregressive Models](https://mlsanity.com/paper/2107.11002/) (2021)

## Built on by (most cited first, 13 of 13)

- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Quantized Low-Rank Multivariate Regression with Random Dithering](https://mlsanity.com/paper/2302.11197/) (2023)
- [Robust Mean Estimation under Quantization](https://mlsanity.com/paper/2601.07074/) (2026)
- [A Parameter-Free Two-Bit Covariance Estimator with Improved Operator Norm Error Rate](https://mlsanity.com/paper/2308.16059/) (2023)
- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Bit Efficient Toeplitz Covariance Estimation](https://mlsanity.com/paper/2412.12678/) (2024)
- [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025)
- [Compressive Toeplitz Covariance Estimation From Few-Bit Quantized Measurements With Applications to DOA Estimation](https://mlsanity.com/paper/2512.22527/) (2025)
- [Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computation](https://mlsanity.com/paper/2602.12982/) (2026)
- [Low-rank Distributional Matrix Completion](https://mlsanity.com/paper/2606.04176/) (2026)
- [One-Bit Clustering for Two Component Sub-Gaussian Mixture Models](https://mlsanity.com/paper/2606.21873/) (2026)

## Abstract (arXiv)

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.