Computing Lewis Weights to High Precision

We present an algorithm for computing approximate ℓ p Lewis weights to high precision. Given a full-rank A ∈ R m×n with m ≥ n and a scalar p > 2, our algorithm computesapproximate ℓ p Lewis weights of A in O p (log(1/ )) iterations; the cost of each iteration is linear in the input size plus the cost of computing the leverage scores of DA for diagonal D ∈ R m×m . Prior to our work, such a computational complexity was known only for p ∈ (0, 4) [CP15], and combined with this result, our work yields the first polylogarithmic-depth polynomial-work algorithm for the problem of computing ℓ 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.