Seminar Details

Seminar Details


Nov 14

4:00 pm

John's Walk

Adam Gustafson

General Exam

We present an affine-invariant random walk for drawing uniform random samples from a convex body for which the maximum volume inscribed ellipsoid, known as John's ellipsoid, may be computed. We consider a polytope where as a special case. Our algorithm makes steps using uniform sampling from the John's ellipsoid of the symmetrization of at the current point. We show that from a warm start, the random walk mixes in steps. This sampling algorithm thus offers improvement over the affine-invariant walk known as the Dikin Walk (which mixes in steps from a warm start) for applications in which . Furthermore, we describe an efficient 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. Finally, we discuss some ideas for improvement of the mixing time analysis, as well as a more efficient algorithm worth exploring for forming approximate ellipsoids.

Time permitting, we may also briefly discuss two other problems of interest. The first problem is an algorithm to round a convex body using affine-invariant random walks such that volume computation may be computed efficiently. The second problem regards high-dimensional interpolation using Whitney's extension theorem.