# On computing approximate Lewis weights

arXiv: https://arxiv.org/abs/2404.02881 · HTML: https://mlsanity.com/paper/2404.02881/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2024.

## Built on by (most cited first, 2 of 2)

- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Active Regression for Single-Index Models with Unknown Link Functions](https://mlsanity.com/paper/2608.01287/) (2026)

## Abstract (arXiv)

In this note we provide and analyze a simple method that given an n × d matrix, outputs approximate ℓp-Lewis weights, a natural measure of the importance of the rows with respect to the ℓp norm, for p ≥ 2. More precisely, we provide a simple post-processing procedure that turns natural one-sided approximate ℓp-Lewis weights into two-sided approximations. When combined with a simple one-sided approximation algorithm presented by Lee (PhD thesis, `16) this yields an algorithm for computing two-sided approximations of the ℓp-Lewis weights of an n × d-matrix using poly(d,p) approximate leverage score computations. While efficient high-accuracy algorithms for approximating ℓp-Lewis had been established previously by Fazel, Lee, Padmanabhan and Sidford (SODA `22), the simple structure and approximation tolerance of our algorithm may make it of use for different applications.