Tight Bounds for Volumetric Spanners in All Norms
summary
A simple single-swap local search provably constructs volumetric spanners for all ℓ_p norms: running until no swap increases det(M) by 1+δ yields a spanner of size at most ≤ 3d in polynomial time (existentially 2d), with iterations O(d log r/δ) and naive cost O(n r d^2) per iteration. Bounds are tight across norms (ℓ1 forces much larger coefficients; ℓ2 and ≥2 give the stated size), and the method produces coreset O(d/ε) guarantees for MVEE.
AI-written summary · about
chapters (8)
- 0:00Volumetric spanners intro
- 1:48Prior work on spanners
- 9:26Local search algorithm
- 19:05Algorithm runtime
- 25:16L2 norm guarantees
- 30:26Other norms and uses
- 33:25Summary and open questions
- 34:54Q&A
related talks
44mStructured Sparsity-Inducing Norms Through Submodular Functions
01h 03mSparsifying Sums of Norms
56mSparsifying Generalized Linear Models
01h 00mTight Bounds for Active lp Regression and Beyond
46mSpectral Partitioning for Metrics (And NNs Too)
45mNoisy Estimation of Simultaneously Structured Models
52mConstrained Subset Selection Problems under Diversity Measures
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces