Computing Lewis Weights to High Precision

Abstract

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\ge n$ and a scalar $p>2$, our algorithm computes $\epsilon$-approximate ${\ell }_p$ Lewis weights of $\mathbf{A}$ in ${\tilde{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{DA}$ 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.

24 pages