Overview
Algorithms have been developed to compute $\epsilon$-estimates of the $\ell_p$-Lewis weights of a matrix $A \in \mathbb{R}^{m \times n}$ for $p \geq 4$. These algorithms utilize $O(p^2 \log(m/\epsilon))$ rounds of leverage score computation.
Research Context
$\ell_p$-Lewis weights and leverage scores are recognized as standard measures for evaluating row importance within a matrix. Prior work by Fazel, Lee, Padmanabha, and Sidford (2022) established a state-of-the-art round complexity of $O(p^3 \log(m/\epsilon))$ for computing such estimates.
Approach
The developed algorithms achieve their results through a specific methodological application. This involves carefully applying a local variant of relatively smooth gradient descent. This variant is applied to both the primal and dual forms of the $\ell_p$-Lewis weight optimization problem. Additionally, the approach incorporates tools designed to facilitate conversion between different notions of approximate $\ell_p$-Lewis weights.
Findings
The algorithms compute $\epsilon$-estimates of the $\ell_p$-Lewis weights for $p \geq 4$. The computation requires $O(p^2 \log(m/\epsilon))$ rounds of leverage score computation. This represents an improvement in round complexity when compared to previous methods, specifically $O(p^3 \log(m/\epsilon))$.