Skip to main content
10 of 10
added 33 characters in body; edited title
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron

A centrally symmetric convex polyhedron in $\Bbb R^n$ shifted from the origin with possibly $e^{\alpha n}$ number of vertices at some $\alpha>0$ has an unique ellipsoid of maximum volume called John's ellipsoid inscribed in it with barycenter of the polyhedron agreeing with center of the ellipsoid.

Obtain an uniform sample of $O(n^c)$ vertices at some fixed $c\geq2$.

  1. Can we apply central limit theorem to approximate barycenter by mean of sample vertices?

  2. Since ellipsoids have only $O(n^2)$ parameters does this sample give a constant fraction approximation of each axis to the ellipsoid?

Turbo
  • 13.9k
  • 1
  • 27
  • 76