Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2

The John ellipsoid of a symmetric polytope $P=\{\mathbf{x}\in {\mathbb{R}}^d:\Vert \mathbf{Ax}{\Vert }_{\infty }\le 1\}$, $\mathbf{A}\in {\mathbb{R}}^{n\times d}$, is computed by a long line…