# A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2014.

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

- [High-dimensional analysis of double descent for linear regression with random projections](https://mlsanity.com/paper/2303.01372/) (2023)
- [Towards a statistical theory of data selection under weak supervision](https://mlsanity.com/paper/2309.14563/) (2023)
- [The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning](https://mlsanity.com/paper/2111.05326/) (2021)
- [Learning Augmentation Distributions using Transformed Risk Minimization](https://mlsanity.com/paper/2111.08190/) (2021)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Sketched Ridgeless Linear Regression: The Role of Downsampling](https://mlsanity.com/paper/2302.01088/) (2023)
- [Variance Alignment Score: A Simple But Tough-to-Beat Data Selection Method for Multimodal Contrastive Learning](https://mlsanity.com/paper/2402.02055/) (2024)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [Ensemble linear interpolators: The role of ensembling](https://mlsanity.com/paper/2309.03354/) (2023)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Sketch to Adapt: Fine-Tunable Sketches for Efficient LLM Adaptation](https://mlsanity.com/paper/2410.06364/) (2024)
- [Linear Discriminant Analysis with the Randomized Kaczmarz Method](https://mlsanity.com/paper/2211.05749/) (2022)
- [DOSE: Data Selection for Multi-Modal LLMs via Off-the-Shelf Models](https://mlsanity.com/paper/2604.16979/) (2026)
- [On Recovering the Best Rank-r Approximation from Few Entries](https://mlsanity.com/paper/2111.06302/) (2021)
- [On the Noise Sensitivity of the Randomized SVD](https://mlsanity.com/paper/2305.17435/) (2023)
- [Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees](https://mlsanity.com/paper/2311.01806/) (2023)
- [Learning nonnegative matrix factorizations from compressed data](https://mlsanity.com/paper/2409.04994/) (2024)
- [Equivariant Test-Time Training with Operator Sketching for Imaging Inverse Problems](https://mlsanity.com/paper/2411.05771/) (2024)
- [SG-OIF: A Stability-Guided Online Influence Framework for Reliable Vision Data](https://mlsanity.com/paper/2511.19466/) (2025)
- [Sequential Preconditioned Conjugate Gradient Method for Linear Statistical Models](https://mlsanity.com/paper/2607.25272/) (2026)
- [Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws](https://mlsanity.com/paper/2610.00101/) (2026)

## Abstract (arXiv)

We consider statistical as well as algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. For a LS problem with input data (X, Y) ∈ ℝn × p × ℝn, sketching algorithms use a sketching matrix, S∈ℝr × n with r ll n. Then, rather than solving the LS problem using the full data (X,Y), sketching algorithms solve the LS problem using only the sketched data (SX, SY). Prior work has typically adopted an algorithmic perspective, in that it has made no statistical assumptions on the input X and Y, and instead it has been assumed that the data (X,Y) are fixed and worst-case (WC). Prior results show that, when using sketching matrices such as random projections and leverage-score sampling algorithms, with p < r ll n, the WC error is the same as solving the original problem, up to a small constant. From a statistical perspective, we typically consider the mean-squared error performance of randomized sketching algorithms, when data (X, Y) are generated according to a statistical model Y = X β + ε, where ε is a noise process. We provide a rigorous comparison of both perspectives leading to insights on how they differ. To do this, we first develop a framework for assessing algorithmic and statistical aspects of randomized sketching methods. We then consider the statistical prediction efficiency (PE) and the statistical residual efficiency (RE) of the sketched LS estimator; and we use our framework to provide upper bounds for several types of random projection and random sampling sketching algorithms. Among other results, we show that the RE can be upper bounded when p < r ll n while the PE typically requires the sample size r to be substantially larger. Lower bounds developed in subsequent results show that our upper bounds on PE can not be improved.