Faster Algorithm for Structured John Ellipsoid Computation

Understand

The famous theorem of Fritz John states that any convex body has a unique maximal volume inscribed ellipsoid, known as the John Ellipsoid.

• Computing the John Ellipsoid is a fundamental problem in convex optimization.
• In this paper, we focus on approximating the John Ellipsoid inscribed in a convex and centrally symmetric polytope defined by $ P := \{ x \in \mathbb{R}^d : -\mathbf{1}_n \leq A x \leq \mathbf{1}_n \},$ where $ A \in \mathbb{R}^{n \times d} $ is a rank-$d$ matrix and $ \mathbf{1}_n \in \mathbb{R}^n $ is the all-ones vector.
• We develop two efficient algorithms for approximating the John Ellipsoid.