Research map / Learning theory and algorithms / Matrix and tensor methods
Faster Algorithms for Structured John Ellipsoid Computation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives two faster algorithms for computing an approximate John Ellipsoid of a centrally symmetric polytope {x: -1 <= Ax <= 1}: a sketching+leverage-score-sampling method with nearly input-sparsity per-iteration cost, and a treewidth-based Cholesky method with O(n tau^2) per-iteration cost.
Problem
Computing the John Ellipsoid (max-volume inscribed ellipsoid) of a symmetric polytope defined by n linear constraints in d dimensions; the prior best per-iteration cost is O(nd^2).
Approach
Speed up the fixed-point Lewis-weight-style iteration of Cohen et al. by combining leverage-score sampling (to sparsify A^T diag(w) A) with Gaussian sketching for the quadratic forms, giving per-iteration cost nearly linear in nnz(A); and for low-treewidth dual graphs, use sparse Cholesky so each iteration costs O(n tau^2).
Key results
- Algorithm runs in O(eps^-1 log(n/d)) iterations with per-iteration cost nearly O(eps^-1 nnz(A) + eps^-2 d^omega), improving on O(nd^2) of prior work.
- Treewidth-based algorithm achieves O(n tau^2) per iteration with the same iteration count, returning a (1+eps)-approximate John Ellipsoid.
- Guarantee: (1/sqrt(1+eps)) Q subset of P subset of sqrt(d) Q for the output ellipsoid.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine leverage-score sampling with sketching instead of the prior fixed-point implementation | John Ellipsoid computation · sparse constraint matrices | cost per iteration: $ n d^2$ -> $\epsilon^{-1} \nnz(A) + \epsilon^{-2} d^{\omega}$ | Helped |
| use the treewidth-based algorithm instead of the prior fixed-point implementation | John Ellipsoid computation · constraint matrices with treewidth $\tau$ | cost per iteration: $ n d^2$ -> $n \tau^2 $ | Helped |
| add leverage-score sampling to the sketching-based approach | Input-sparsity algorithm · John Ellipsoid computation | running time: $O(nd^2)$ -> $\widetilde{O}(\epsilon^{-1}\mathrm{nnz}(A) + \epsilon^{-2} d^{\omega})$ | Helped |
| use small-treewidth Cholesky factorization | Treewidth-based algorithm · John Ellipsoid computation with treewidth $\tau$ | running time: $O(nd^2)$ -> $O(n \tau^2)$ | Helped |
Limitations
- No experimental evaluation; results are purely theoretical running-time and correctness analyses.
- Treewidth algorithm only helps when the dual graph has small treewidth; the paper notes this is a stricter condition than input sparsity.
- Sketching/sampling introduce randomness and failure probability; the nearly input-sparsity bound hides log(d/delta) factors.
Experimental setup
Metrics: per-iteration running time approximation factor of John Ellipsoid
Baselines: Cohen et al. COLT 2019 fixed-point John Ellipsoid algorithm
Builds on: Cohen-Cousins-Lee-Yang fixed-point John Ellipsoid algorithm (COLT 2019) matrix Chernoff bound leverage score sampling
Closest papers by meaning
- John Ellipsoids via Lazy Updates (NeurIPS 2024 · similarity 0.91)
- Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs (NeurIPS 2026 · similarity 0.80)
- Decentralized Projected Riemannian Stochastic Recursive Momentum Method for Nonconvex Optimization (AAAI 2025 · similarity 0.80)
- ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS (ICLR 2025 · similarity 0.80)
- Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (NeurIPS 2024 · similarity 0.80)
- Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing (NeurIPS 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.