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 : -\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. The first is a sketching-based algorithm that runs in nearly input-sparsity time $\widetilde{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 $\widetilde{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 $\widetilde{O}(n d^2)$ achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019].