On computing approximate Lewis weights
<|reference_start|>On computing approximate Lewis weights: In this note we provide and analyze a simple method that given an $n \times d$ matrix, outputs approximate $\ell_p$-Lewis weights, a natural measure of the importance of the rows with respect to the $\ell_p$ norm, for $p \geq 2$. More precisely, we provide a simple post-processing procedure that turns natural one-sided approximate $\ell_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 $\ell_p$-Lewis weights of an $n \times d$-matrix using $\mathrm{poly}(d,p)$ approximate leverage score computations. While efficient high-accuracy algorithms for approximating $\ell_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.<|reference_end|>
@article{apers2024on,
    title={On computing approximate Lewis weights},
    author={Simon Apers, Sander Gribling, Aaron Sidford},
    journal={arXiv preprint arXiv:2404.02881},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.02881},
    primaryClass={cs.DS math.OC}
}