Computing Lewis weights to high precision using local relative smoothness

Sander Gribling, Aaron Sidford, Chenyi Zhang

We provide algorithms that compute $\hat{I}\mu$-estimates of the ${\ell }_p$-Lewis weights of a matrix $A\in {\mathbb{R}}^{m\times n}$ for $p\ge 4$ using $O(p^2\log (m/\hat{I}\mu ))$ rounds of lever…