Faster Algorithms for Structured John Ellipsoid Computation

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:-1_n\le Ax\le 1_n\},$ where $A\in {\mathbb{R}}^{n\times d}$ is a rank-$d$ matrix and $1_n\in {\mathbb{R}}^n$ is the all-ones vector.

We develop two efficient algorithms for approximating the John Ellipsoid. The first is a sketching-based algorithm that runs in nearly input-sparsity time $O(\mathrm{nnz}(A)+d^{\omega })$, where $\mathrm{nnz}(A)$ denotes the number of nonzero entries in the matrix $A$ and $\omega \approx 2.37$ is the current matrix multiplication exponent. The second is a treewidth-based algorithm that runs in time $O(n{\tau }^2)$, where $\tau$ is the treewidth of the dual graph of the matrix $A$.

Our algorithms significantly improve upon the state-of-the-art running time of $O(n{d}^2)$ achieved by Cohen, Cousins, Lee, and Yang, COLT 2019.