# 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? – 1.. May 12 '17 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? – Yoav Kallus May 12 '17 at 19:50
• @YoavKallus clarified. – 1.. May 12 '17 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. – Joseph O'Rourke May 12 '17 at 20:14

## 1 Answer

No, a fixed number of added vertices can change the John ellipsoid by an arbitrary amount when added to arbitrarily many already known vertices: consider a very thin regular n-gon prism centered about the origin. Now we can add two new vertices in a way that doesn't change the polyhedron much (near existing vertices, say), or we can add two new vertices along the axis of the prism very far away from it (in a symmetric way, so that the polyhedron is still centered about the origin). The two possibilities have very different John ellipsoids, so you cannot approximate the John ellipsoid before knowing where these vertices are.

If you are sampling the vertices uniformly at random, then you have a good chance of missing the two crucial ones out of the many noncrucial ones.

• Yes. But I am sampling a centrally symmetric polytope which already has a structure. So the drastic changes you suggest may be unlikely event. right? – 1.. May 13 '17 at 1:43