We present a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result provides a constructive proof for the Approximate Caratheodory Problem (Barman, 2015), which states that any point inside a polytope contained in the l_p ball of radius D can be approximated to within ε in l_p norm by a convex combination of O (D~2p/ε~2) vertices of the polytope for p ≥ 2. While for the particular case of p = 2, this can be achieved by the well-known Perceptron algorithm, we follow a more principled approach which generalizes to arbitrary p ≥ 2; furthermore, this naturally extends to domains with more complicated geometry, as it is the case for providing an approximate Birkhoff-von Neumann decomposition. Secondly, we show that the sparsity bound is tight for l_p norms, using an argument based on anti-concentration for the binomial distribution, thus resolving an open question posed by Barman. Experimentally, we verify that our deterministic optimization-based algorithms achieve in practice much better sparsity than previously known sampling-based algorithms. We also show how to apply our techniques to SVM training and rounding fractional points in matroid and flow polytopes.
展开▼
