Thrifty approximations of convex bodies by polytopes

By Alexander I. Barvinok. 2012

62 citations recorded by the source corpus.

Given a convex body C in R^d containing the origin in its interior and a real number tau > 1 we seek to construct a polytope P in C with as few vertices as possible such that C in tau P. Our construction is nearly optimal for a wide range of d and tau. In particular, we prove that if C=-C then for any 1>epsilon>0 and tau=1+epsilon one can choose P having roughly epsilon^{-d/2} vertices and for tau=sqrt{epsilon d} one can choose P having roughly d^{1/epsilon} vertices. Similarly, we prove that if C in R^d is a convex body such that -C in mu C for some mu > 1 then one can choose P having roughly ((mu+1)/(tau-1))^{d/2} vertices provided (tau-1)/(mu+1) << 1.

Subfields: Applied Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/adbec00d5b45281a9e178ed7a18ac6b2ada63a0e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

Uniform post-selection inference for least absolute deviation regression and other Z-estimation problems (2013, background): “5 in [4] as if Aq was a set in Rsq shows that one can construct a polytope Pq ⊂ Rp with at most (γ((μ + 1)/ε)1/2 log(1/ε))sq vertices such that Pq ⊂ Aq ⊂ (1 + ε)Pq and such that for all v ∈ V(Pq), non-zero elements of v correspond to some of the main components of Aq.”
Central limit theorems and bootstrap in high dimensions (2014, background): “Therefore, applying Corollary 1.5 in [4] as if A q was a set in R s q shows that one can construct a polytope P q ⊂ R p with at most ( γ (( µ + 1) /ǫ ) 1 / 2 log(1 /ǫ )) s q vertices such that P q ⊂ A q ⊂ (1 + ǫ ) P q and such that for all v ∈ V ( P q ), non-zero elements of v correspond to some of…”