Dynamic Weighted Projection Maintenance with $\ell^p$-Lewis Weight

Yang Cao, Xiaoyu Li, Zhao Song, Jiale ZhaoOpenReview 2026 · Submission to ICLR 2026 · Rejected · OpenReview

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},
}
Figure