  We present an algorithm for computing approximate $\ell_p$ Lewis weights to
high precision. Given a full-rank $\mathbf{A} \in \mathbb{R}^{m \times n}$ with
$m \geq n$ and a scalar $p>2$, our algorithm computes $\epsilon$-approximate
$\ell_p$ Lewis weights of $\mathbf{A}$ in $\widetilde{O}_p(\log(1/\epsilon))$
iterations; the cost of each iteration is linear in the input size plus the
cost of computing the leverage scores of $\mathbf{D}\mathbf{A}$ for diagonal
$\mathbf{D} \in \mathbb{R}^{m \times m}$. Prior to our work, such a
computational complexity was known only for $p \in (0, 4)$ [CohenPeng2015], and
combined with this result, our work yields the first polylogarithmic-depth
polynomial-work algorithm for the problem of computing $\ell_p$ Lewis weights
to high precision for all constant $p > 0$. An important consequence of this
result is also the first polylogarithmic-depth polynomial-work algorithm for
computing a nearly optimal self-concordant barrier for a polytope.
