Jul 2026
A Matrix Factorization Approach in Turnstile Streaming
We define the $M$-point query problem in data streams. Given a fixed matrix $M$, the goal is to maintain a vector $x$ under turnstile updates and answer each query $u$ with an estimate $\widehat{y}_u$ satisfying $|y_u-\widehat{y}_u| \leq \varepsilon \|x\|_1$, where $y=Mx$. We show that if $M$ admits a factorization $M=...
Jan Bulánek, Ravi Kumar, Raghu Meka et al.
· arXiv.org · 1 citation
· ⚡1