Sparse sketches with small inversion bias

For a tall n× d matrix A and a random m× n sketching matrix S, the sketched estimate of the inverse covariance matrix (A^top A)-1 is typically biased: E[(tilde A^toptilde A)-1]ne(A^top A)-1, where tilde A=SA. This phenomenon, which we call inversion bias, arises, e.g., in statistics and distributed optimization, when averaging multiple independently constructed estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an (ε,δ)-unbiased estimator for random matrices. We show that when the sketching matrix S is dense and has i.i.d. sub-gaussian entries, then after simple rescaling, the estimator (frac mm-dtilde A^toptilde A)-1 is (ε,δ)-unbiased for (A^top A)-1 with a sketch of size m=O(d+√ d/ε). This implies that for m=O(d), the inversion bias of this estimator is O(1/√ d), which is much smaller than the Theta(1) approximation error obtained as a consequence of the subspace embedding guarantee for sub-gaussian sketches. We then propose a new sketching technique, called LEverage Score Sparsified (LESS) embeddings, which uses ideas from both data-oblivious sparse embeddings as well as data-aware leverage-based row sampling methods, to get ε inversion bias for sketch size m=O(dlog d+√ d/ε) in time O(nnz(A)log n+md2), where nnz is the number of non-zeros. The key techniques enabling our analysis include an extension of a classical inequality of Bai and Silverstein for random quadratic forms, which we call the Restricted Bai-Silverstein inequality; and anti-concentration of the Binomial distribution via the Paley-Zygmund inequality, which we use to prove a lower bound showing that leverage score sampling sketches generally do not achieve small inversion bias.