# 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?

• so why negative vote? May 12, 2017 at 19:43
• (Not the downvote, but) I think your question is unclear, at least to me. Specifically what does it mean for the convex hull of some vertices of the polytope to "determine" the ellipsoid. Can you provide an example? May 12, 2017 at 19:50
• @YoavKallus clarified. May 12, 2017 at 20:01
• It seems to me that the $k=O(n^2)$ parameters that determine an ellipsoid can be achieved by $k$ facets tangent to the ellipsoid. So your question is easier to answer in terms of facets than in terms of vertices. One could certainly dispense with all the vertices that are not incident to a facet tangent to the ellipsoid. May 12, 2017 at 20:14