A covariance matrix estimator using two bits per entry was recently developed
by Dirksen, Maly and Rauhut [Annals of Statistics, 50(6), pp. 3538-3562]. The
estimator achieves near minimax 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, thus closing the theoretical gap. Moreover, our proposed
method eliminates the need of any tuning parameter, as the dithering scales are
entirely determined by the data. Experimental results under Gaussian samples
are provided to showcase the impressive numerical performance of our estimator.
Remarkably, by halving the dithering scales, our estimator oftentimes achieves
operator norm errors less than twice of the errors of sample covariance.

我们提出了一种新的 2 位协方差矩阵估计器，通过采用三角形 dither 先于 2 位量化器，可以同时解决 Dirksen 等人的两个问题，提高了算子范数误差率，并且无需任何调整参数，实验结果证明了估计器的出色数值性能。