Computing Lewis Weights to High Precision

We present an algorithm for computing approximate ℓp Lewis weights to high precision. Given a full-rank A ∈ ℝm × n with m ≥ n and a scalar p>2, our algorithm computes ε-approximate ℓp Lewis weights of A in widetildeOp(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 ∈ ℝm × m. Prior to our work, such a computational complexity was known only for p ∈ (0, 4) [CohenPeng2015], 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.