Tight Bounds for Volumetric Spanners and Applications
This work addresses a foundational problem in computational geometry and optimization with applications in bandit linear optimization and matrix approximation, but it appears incremental as it builds on existing notions of volumetric spanners.
The paper tackles the problem of finding volumetric spanners, which are subsets of points that can represent all points with small coefficients, and provides almost optimal bounds on their size for all ℓp norms, showing they can be constructed via local search. It applies these results to tasks like coresets for the Minimum Volume Enclosing Ellipsoid problem.
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 = \{v_1, v_2, \dots, v_n\}$, the goal is to find $T \subseteq [n]$ such that every $v \in X$ can be expressed as $\sum_{i\in T} α_i v_i$, 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 $\ell_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.