Dynamic Weighted Projection Maintenance with $\ell^p$-Lewis Weight
Lists
Only you see this
Abstract
We introduce a new data–structure problem—\emph{Dynamic $\ell_{p}$-Lewis Weight Projection Maintenance}—that asks us to maintain the projection \begin{align*} P(W) = W^{1/2-1/p}\,A(A^{\top}W^{1-2/p}A)^{-1}A^{\top}W^{1/2-1/p} \end{align*} under a stream of diagonal weight updates and to support fast matrix–vector products with $P(W)$. This setting strictly generalizes the $\sqrt{W}A$ projection, which is at the heart of state-of-the-art linear programming and interior point methods, and it captures a wide range of algorithms that rely on leverage scores or Lewis weights for sampling and preconditioning. We provide a deterministic projection-maintenance data structure with sublinear amortized updates. Moreover, we extend it to the differential privacy setting.
BibTeX
@misc{cao2026dynamic,
author = {Yang Cao and Xiaoyu Li and Zhao Song and Jiale Zhao},
title = {{Dynamic Weighted Projection Maintenance with $\textbackslash\{\}ell^p$-Lewis Weight}},
year = {2026},
url = {https://openreview.net/forum?id=HaQ5PCJOiU},
howpublished = {OpenReview},
note = {Submitted to ICLR 2026},
}