# Sparse sketches with small inversion bias

arXiv: https://arxiv.org/abs/2011.10695 · HTML: https://mlsanity.com/paper/2011.10695/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2020.

## Built on by (most cited first, 19 of 19)

- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Monotonicity and Double Descent in Uncertainty Estimation with Gaussian Processes](https://mlsanity.com/paper/2210.07612/) (2022)
- [Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning](https://mlsanity.com/paper/2310.04357/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation](https://mlsanity.com/paper/2103.04031/) (2021)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs](https://mlsanity.com/paper/2206.10291/) (2022)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [Learning Linear Models Using Distributed Iterative Hessian Sketching](https://mlsanity.com/paper/2112.04101/) (2021)
- [Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints](https://mlsanity.com/paper/2304.10123/) (2023)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

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.