On computing approximate Lewis weights

Simon Apers, Sander Gribling, Aaron Sidford

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 w…