Faster Algorithm 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 ∈ ℝd : -1n ≤ A x ≤ 1n , where A ∈ ℝn × d is a rank-d matrix and 1n ∈ ℝ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 widetildeO(nnz(A) + dω) , where nnz(A) denotes the number of nonzero entries in the matrix A and ω ≈ 2.37 is the current matrix multiplication exponent. The second is a treewidth-based algorithm that runs in time widetildeO(n τ2), where τ is the treewidth of the dual graph of the matrix A. Our algorithms significantly improve upon the state-of-the-art running time of widetildeO(n d2) achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019].