2022/11/26 by Cao, Yang, Zhao Song, Li, Xiaoyu +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Numerical Methods and Algorithms #Parallel Computing and Optimization Techniques #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2211.14407
openalex publication_date 2022/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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].