Faster algorithms for polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"
share
We study the problem of "isotropically rounding" a polytope K⊆R^n, that is, computing a linear transformation which makes the uniform distribution on the polytope have roughly identity covariance matrix. We assume that K is defined by m linear inequalities, with guarantee that rB⊆ K⊆ RB, where B is the unit ball. We introduce a new variant of the ball walk Markov chain and show that, roughly, the expected number of arithmetic operations per-step of this Markov chain is O(m) that is sublinear in the input size mn--the per-step time of all prior Markov chains. Subsequently, we give a rounding algorithm that succeeds with probability 1-ε in Õ(mn^4.5polylog(1/ε,R/r)) arithmetic operations. This gives a factor of √(n) improvement on the previous bound of Õ(mn^5polylog(1/ε,R/r)) for rounding, which uses the hit-and-run algorithm. Since the cost of the rounding preprocessing step is in many cases the bottleneck in improving sampling or volume computation, our results imply these tasks can also be achieved in roughly Õ(mn^4.5polylog(1/ε,R/r)+mn^4δ^-2) operations for computing the volume of K up to a factor 1+δ and Õ(m n^4.5polylog(1/ε,R/r))) for uniformly sampling on K with TV error ε. This improves on the previous bounds of Õ(mn^5polylog(1/ε,R/r)+mn^4δ^-2) for volume computation and Õ(mn^5polylog(1/ε,R/r)) for sampling. We achieve this improvement by a novel method of computing polytope membership, where one avoids checking inequalities which are estimated to have a very low probability of being violated.
READ FULL TEXT