High Dimensional Statistical Estimation under Uniformly Dithered One-Bit Quantization

Junren Chen*, Cheng Long Wang, Michael K. Ng*, Di Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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 minimax rates up to logarithmic factors, 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 represents the first method robust to pre-quantization noise with unknown distribution. Experimental results on synthetic data are presented to support our theoretical analysis.

Original languageEnglish (US)
Pages (from-to)5151-5187
Number of pages37
JournalIEEE Transactions on Information Theory
Volume69
Issue number8
DOIs
StatePublished - Aug 1 2023

Keywords

  • Compressed sensing
  • heavy-tailed data
  • matrix completion
  • quantization

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'High Dimensional Statistical Estimation under Uniformly Dithered One-Bit Quantization'. Together they form a unique fingerprint.

Cite this