Faster polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"

arXiv1905.01745MaRDI QIDQ6318239FDOQ6318239

Authors: Oren Mangoubi, Nisheeth K. Vishnoi

Publication date: 5 May 2019

Abstract: We study the problem of "isotropically rounding" a polytope

K s u b s e t m a t h b b R^{n}

, that is, computing a linear transformation which makes the uniform distribution on the polytope have roughly identity covariance matrix. We assume

K

is defined by

m

linear inequalities, with guarantee that

r B s u b s e t K s u b s e t R B

, 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

m n

--the per-step time of all prior Markov chains. Subsequently, we give a rounding algorithm that succeeds with probability

1 - v a r e p s i l o n

in

i l d e O (m n^{4.5} m b o x p o l y l o g (f r a c 1 v a r e p s i l o n, f r a c R r))

arithmetic operations. This gives a factor of

s q r t n

improvement on the previous bound of

i l d e O (m n^{5} m b o x p o l y l o g (f r a c 1 v a r e p s i l o n, f r a c R r))

for rounding, which uses the hit-and-run algorithm. Since 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

i l d e O (m n^{4.5} m b o x p o l y l o g (f r a c 1 v a r e p s i l o n, f r a c R r) + m n^{4} d e l t a^{- 2})

operations for computing the volume of

K

up to a factor

1 + d e l t a

and

i l d e O (m n^{4.5} m b o x p o l y l o g (f r a c 1 v a r e p s i l o n, f r a c R r)))

for uniformly sampling on

K

with TV error

v a r e p s i l o n

. This improves on the previous bounds of

i l d e O (m n^{5} m b o x p o l y l o g (f r a c 1 v a r e p s i l o n, f r a c R r) + m n^{4} d e l t a^{- 2})

for volume computation when roughly

m g e q n^{2.5}

, and

i l d e O (m n^{5} m b o x p o l y l o g (f r a c 1 v a r e p s i l o n, f r a c R r))

for sampling when roughly

m g e q n^{1.5}

. We achieve this improvement by a novel method of computing polytope membership, where one avoids checking inequalities estimated to have a very low probability of being violated.

This page was built for publication: Faster polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318239)