We present an affine-invariant random walk for drawing uniform random samples from a convex body K \subset R^n for which the maximum volume inscribed ellipsoid , known as John's ellipsoid, may be computed. We consider a polytope \mathcal{P = \{x \in R^n \mid Ax \leq 1\} where A \in R^{m \times n} as a special case. }  Our algorithm makes steps using uniform sampling from the John's ellipsoid of the symmetrization of K at the current point. We show that from a warm start, the random walk mixes in O(n^7) steps where the log factors depend only on constants determined by the warm start and error parameters (and not on the dimension or number of constraints defining the body). This sampling algorithm thus offers improvement over the affine-invariant Dikin Walk for polytopes (which mixes in (mn) steps from a warm start) for applications in which m \gg n. Furthermore, we describe an%DIFDELCMD < \widetilde{O}%%% (mn^{\omega+1 + n^{2\omega+2}) algorithm for finding a suitably approximate John's ellipsoid for a symmetric polytope based on Vaidya's algorithm, and show the mixing time is retained using these approximate ellipsoids (where \omega < 2.373 is the current value of the fast matrix multiplication constant)}  containing x, }\\{|q-x|}\ is bounded above by a polynomial in n} .
We present an affine-invariant random walk for drawing uniform random samples from a convex body K \subset R^n that uses maximum volume inscribed ellipsoids , known as John's = \{x \in R^n \mid Ax \leq 1\} where A \in R^{m \times n} as a special case. } ellipsoids, for the proposal distribution. Our algorithm makes steps using uniform sampling from the John's ellipsoid of the symmetrization of K at the current point. We show that from a warm start, the random walk mixes in O(n^7) steps where the log factors depend only on constants associated with the warm start and %DIFDELCMD < \widetilde{O}%%% + n^{2\omega+2}) algorithm for finding a suitably approximate John's ellipsoid for a symmetric polytope based on Vaidya's algorithm, and show the mixing time is retained using these approximate ellipsoids (where \omega < 2.373 is the current value of the fast matrix multiplication constant)} desired total variation distance to uniformity. We also prove polynomial mixing bounds starting from any fixed point x such that for any chord pq of \mathcal{K containing x, }\\log \frac{|p-x|{|q-x|}\ is bounded above by a polynomial in n} .
R
for which the
that uses
R
ellipsoid
ellipsoids
D
ellipsoid, may be computed. We consider a polytope \mathcal{P
A
ellipsoids, for the proposal distribution.
R
determined by
associated with
D
error parameters (and not on the dimension or number of constraints defining the body). This sampling algorithm thus offers improvement over the affine-invariant Dikin Walk for polytopes (which mixes in
D
(mn) steps from a warm start) for applications in which m \gg n. Furthermore, we describe an
D
(mn^{\omega+1
A
desired total variation distance to uniformity. We also prove polynomial mixing bounds starting from any fixed point x such that for any chord pq of \mathcal{K
A
log \frac{|p-x|