A Parameter-Free Two-Bit Covariance Estimator with Improved Operator
  Norm Error Rate
Junren Chen Michael K. Ng
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.