# Unbiased estimates for linear regression via volume sampling

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2017.

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

- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD](https://mlsanity.com/paper/2112.06007/) (2021)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Data Selection for ERMs](https://mlsanity.com/paper/2504.14572/) (2025)
- [Exact Risk Ratios for Weighted Data Selection in Linear Regression](https://mlsanity.com/paper/2608.28007/) (2026)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [Adaptive randomized pivoting and volume sampling](https://mlsanity.com/paper/2510.02513/) (2025)
- [Semi-supervised Active Regression](https://mlsanity.com/paper/2106.06676/) (2021)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression](https://mlsanity.com/paper/2608.30254/) (2026)

## Abstract (arXiv)

Given a full rank matrix X with more columns than rows, consider the task of estimating the pseudo inverse X^+ based on the pseudo inverse of a sampled subset of columns (of size at least the number of rows). We show that this is possible if the subset of columns is chosen proportional to the squared volume spanned by the rows of the chosen submatrix (ie, volume sampling). The resulting estimator is unbiased and surprisingly the covariance of the estimator also has a closed form: It equals a specific factor times X+topX^+. Pseudo inverse plays an important part in solving the linear least squares problem, where we try to predict a label for each column of X. We assume labels are expensive and we are only given the labels for the small subset of columns we sample from X. Using our methods we show that the weight vector of the solution for the sub problem is an unbiased estimator of the optimal solution for the whole problem based on all column labels. We believe that these new formulas establish a fundamental connection between linear least squares and volume sampling. We use our methods to obtain an algorithm for volume sampling that is faster than state-of-the-art and for obtaining bounds for the total loss of the estimated least-squares solution on all labeled columns.