# Tight Bounds for Volumetric Spanners and Applications

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 40 references that are in the map.
- First posted on arXiv 29 Sep 2023.

## Builds on (most cited first, 9 of 9)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [New Subset Selection Algorithms for Low Rank Approximation: Offline and Online](https://mlsanity.com/paper/2304.09217/) (2023)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm](https://mlsanity.com/paper/1907.03197/) (2019)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)

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

- [Contextual Linear Bandits with Delay as Payoff](https://mlsanity.com/paper/2502.12528/) (2025)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach](https://mlsanity.com/paper/2602.06404/) (2026)

## Abstract (arXiv)

Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate norm). Formally, given a set of vectors X = v1, v2, dots, vn, the goal is to find T subseteq [n] such that every v ∈ X can be expressed as sumi∈ T αi vi, with |α| being small. This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, determinant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all ℓp norms, and show that they can be constructed using a simple local search procedure. We then show the applications of our result to other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.