A parameter-free two-bit covariance estimator with improved operator norm error rate

A covariance matrix estimator using two bits per entry was recently developed by Dirksen et al. (2022) [11]. The estimator achieves near minimax operator norm rate for general sub-Gaussian distributions, but also suffers from two downsides: theoretically, there is an essential gap on operator norm error between their estimator and sample covariance when the diagonal of the covariance matrix is dominated by only a few entries; practically, its performance heavily relies on the dithering scale, which needs to be tuned according to some unknown parameters. In this work, we propose a new 2-bit covariance matrix estimator that simultaneously addresses both issues. Unlike the sign quantizer associated with uniform dither in Dirksen et al., we adopt a triangular dither prior to a 2-bit quantizer inspired by the multi-bit uniform quantizer. By employing dithering scales varying across entries, our estimator enjoys an improved operator norm error rate that depends on the effective rank of the underlying covariance matrix rather than the ambient dimension, which is optimal up to logarithmic factors. Moreover, our proposed method eliminates the need of any tuning parameter, as the dithering scales are entirely determined by the data. While our estimator requires a pass of all unquantized samples to determine the dithering scales, it can be adapted to the online setting where the samples arise sequentially. Experimental results are provided to demonstrate the advantages of our estimators over the existing ones.