John Ellipsoids via Lazy Updates

David P. Woodruff, Taisuke Yasuda

We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the le…