A Matrix Factorization Approach in Turnstile Streaming

Source: arXiv:2607.28819 · Published 2026-07-30 · By Jan Bulanek, Ravi Kumar, Raghu Meka, Jelani Nelson, Tamas Sarlos

TL;DR

This paper introduces a general framework for the M-point query problem in turnstile streaming models, where the goal is to maintain an approximate vector y = Mx under arbitrary insertions/deletions to x, so that queries y_u can be answered within additive error ε||x||_1. The major advance is showing that if the query matrix M can be factorized as M = AB with factors A and B having efficient (norm-based) representations, then there is a streaming algorithm using space proportional to ε^{-1} times norms of A and B. Applying this to the prefix-sum (lower-triangular all ones) matrix Q gives improved and simplified algorithms for turnstile quantile estimation, reducing space from prior O(ε^{-1} log^{3/2} U polylog factors) to O(ε^{-1} log^{3/2} U). The factorization viewpoint also provides nearly matching lower bounds on such norms, showing the dyadic CountSketch approach is near-optimal among factorization approaches. A new information-theoretic Ω(ε^{-1} log U) lower bound is proved for quantiles with deletions, separating fully dynamic from insertion-only streaming. The work unifies and improves the understanding of streaming quantile algorithms and their fundamental limits through matrix factorization and refined sketching analyses.

Key findings

• If M = AB and A, B have small operator norms, there exists a streaming algorithm with memory O(ε^{-1}||A||_{2→∞}||B||_{1→1} + (ε^{-1}||A||_{∞→∞}||B||_{1→1})^{2/3}) words.
• For the prefix-sum (quantiles) matrix Q, the classical dyadic factorization has ||A||_{2→∞} ≤ √log U, ||A||_{∞→∞} ≤ log U, ||B||_{1→1} ≤ log U, yielding a streaming algorithm using O(ε^{-1} log^{3/2} U) words.
• Their CountSketch error correlation bound (Theorem 2.1) improves prior analyses by showing E[err(u)·err(v)] = O(ε^{3})||x||_1^2, enabling aggregation of errors across all dyadic levels with a single CountSketch instance.
• They prove an unconditional memory lower bound of Ω(ε^{-1} log U) words for any streaming algorithm answering quantile queries with deletions, improving on prior insertion-only lower bounds of Ω(1/ε).
• Any factorization M=AB of Q satisfies ||A||_{2→∞}||B||_{1→1} = Ω((log^{1.5} U)/log log U), near matching the classical dyadic upper bound, so factorization-based methods cannot improve space complexity substantially.
• Their algorithm matches or improves on prior dyadic CountSketch algorithms (Wang et al. SIGMOD 2013, Luo et al. VLDB 2016) by simplifying to using a single CountSketch table and tightening bounds by avoiding union bounds.
• The factorization perspective connects to the matrix mechanism in differential privacy; minimizing ||A||_{2→∞}||B||_{1→1} governs the privacy-error tradeoff but closing gaps in pure-DP bounds needs more than factorization improvements.
• Their rigorous pseudorandomness analysis enables practical implementation with limited independence and PRGs fooling intersections of halfspaces.

Threat model

The adversary is an adaptive data stream that updates the frequency vector x arbitrarily under the turnstile model—i.e., inserts and deletes elements at any coordinate. The algorithm must maintain a space-efficient sketch without storing x explicitly. The adversary cannot observe randomness internal to the sketch or interfere with its state. Queries are made after processing the stream and the goal is to return accurate approximate query answers with high probability. The adversary does not have oracle access to the challenge output beyond the streaming updates. Adversarial capabilities include input deletion and insertion but not cryptographic attacks or side channels.

Methodology — deep read

1. Threat Model and Assumptions: The adversary is the data stream itself, which performs arbitrary turnstile updates (insertions and deletions) to the frequency vector x over a universe [U]. The goal is to design streaming algorithms that maintain a compact sketch to estimate linear queries y = Mx with additive error scaled by ε||x||_1 with high probability. The matrix M is fixed and known in advance, and factorizes as M = AB. The streaming computation must be space efficient (sub-linear in U), and handle fully dynamic turnstile updates. 2. Data: The input is a data stream over universe [U], each element generating updates (u, Δ) to x_u. The size of x is dynamic but the algorithms do not rely on explicit data storage. Queries correspond to rows u ∈ [U] of the vector y = Mx. The strict turnstile model requires that entries of x stay non-negative, important for quantiles. No explicit training data; the problem is streaming estimation. 3. Algorithmic Architecture: The algorithm sketches the vector z = Bx using a CountSketch data structure, a classic ℓ_2 / ℓ_1 approximate frequency sketch with parameters (number of hash rows ℓ=5 and number of buckets per row r=Θ(1/ε)). It recovers an estimate bz of Bx from CountSketch using median-of-5 estimators per coordinate. The final approximation is produced as by = A · bz. The crucial novelty is bounding correlations between CountSketch errors to control the propagation of error through multiplication by A. The CountSketch randomness is carefully derandomized using pseudorandom generators that fool intersections of halfspaces, guaranteeing strong concentration with limited independence. 4. Training Regime: Not a learning algorithm—no training epochs or hyperparameters in the ML sense. Sketch parameters (r, ℓ) chosen based on ε and operator norms of A, B. Updates are processed online in O(log U) time (due to B’s sparsity in the dyadic factorization). 5. Evaluation Protocol: They analyze the mean squared error of the estimator for each query coordinate u. They prove that with probability at least 2/3, |y_u - by_u| ≤ ε ||x||_1 by combining variance and covariance bounds of CountSketch errors with operator norm bounds of A and B. They also prove information-theoretic lower bounds using reductions from communication complexity (augmented indexing problem), showing any streaming algorithm for quantiles with deletions must use Ω(ε^{-1} log U) words. Further, they prove impossibility results for factorization improvements by using martingale concentration and functional-analytic arguments on the norms of factorizations. 6. Reproducibility: The algorithms build on classical CountSketch and explicit dyadic tree factorizations well documented in previous literature. No closed datasets are used, only streaming APIs. Code release is not mentioned. The pseudorandomness constructions rely on known PRGs from [GOWZ10, GKM18, JW21]. The analyses are mathematically rigorous and self-contained in the paper. Concrete example end-to-end: For rank/quantile queries, M = Q is the lower-triangular all ones prefix-sum matrix over U items. Q is factorized via dyadic decomposition into sparse A, B with norms bounded by log U and √log U factors. The algorithm maintains a single CountSketch on Bx, estimates bz from it, then computes the final query approximation as A · bz, giving additive error ε ||x||_1 with memory O(ε^{-1} log^{3/2} U). This improves prior papers requiring separate sketches per dyadic level. The key technical advancement is the novel correlation bound for CountSketch errors (Theorem 2.1) enabling this aggregation. The lower bound (Theorem 5.1) uses a reduction from augmented indexing communication complexity, encoding codewords into stream blocks and recovering them through quantile queries from the sketch, proving space must scale as Ω(ε^{-1} log U).

Technical innovations

• Novel error correlation bound for median-of-5 CountSketch showing covariance between distinct coordinate errors decays as O(ε^{3}), enabling use of a single CountSketch instance to cover all dyadic intervals simultaneously.
• A general streaming algorithm for M-point query problems based on matrix factorization M = AB with provable space bounds depending on operator norms ||A||_{2→∞}, ||A||_{∞→∞}, and ||B||_{1→1}.
• An improved and simplified analysis of turnstile quantile streaming, reducing space from O(ε^{-1} log^{3/2} U polylog factors) to O(ε^{-1} log^{3/2} U) and requiring only one CountSketch data structure instead of many per tree level.
• A new, nearly tight lower bound on the matrix factorization norms of the prefix-sum matrix Q, showing no factorization can improve over dyadic factorization by more than a log log U factor.
• A strong information-theoretic Ω(ε^{-1} log U) lower bound for quantile streaming with deletions (turnstile model), showing an inherent logarithmic separation from insertion-only models.

Baselines vs proposed

• Prior work dyadic CountSketch [LWYC16]: space = O(ε^{-1} log^{3/2} U (log (ε^{-1} log U))^{3/2}) words; proposed: O(ε^{-1} log^{3/2} U) words
• Insertion-only quantiles [GSW24]: space = O(ε^{-1}) words; turnstile with deletions (this paper): Ω(ε^{-1} log U) words lower bound
• Trivial decomposition M=I, B=Q: space Ω(U/ε) words for additive error ε n; dyadic factorization: O(ε^{-1} log^{3/2} U) words
• Factorization lower bound γ_{2,1}(Q) = Ω((log^{1.5} U) / log log U) vs dyadic factorization upper bound O(log^{1.5} U)

Limitations

• The algorithm and analysis require the matrix M to have a factorization M=AB with reasonably bounded operator norms; matrices lacking such structure fall outside the framework.
• The space bounds exclude storage of the factorization matrices A and B themselves, assuming they can be stored implicitly or computed on the fly; this may limit applicability in some settings.
• The lower bounds focus only on factorization-based approaches, so other fundamentally different algorithms could theoretically improve space usage, though none are known.
• The CountSketch construction and pseudorandomness require careful implementation details (e.g., PRGs fooling halfspace intersections) that may complicate engineering deployment.
• Analysis and bounds hold for additive error proportional to ||x||_1, which may be loose for very skewed data distributions where other norms would be more natural.
• The strong lower bound for turnstile quantiles applies to worst-case streams; practical scenarios with structured inputs might admit better algorithms.

Open questions / follow-ons

• Can the Ω(ε^{-1} log U) lower bound for turnstile quantiles be further tightened, closing the remaining √log U gap between upper and lower bounds?
• Is there a fundamental algorithmic approach beyond matrix factorization that can yield streaming quantile estimation with better space than dyadic CountSketch?
• Can the matrix factorization norms ||A||_{2→∞} ||B||_{1→1} be improved by alternative factorizations for other natural streaming queries beyond quantiles?
• How do factorization approaches extend to more complex functions Mx relevant in practice, e.g., time-decayed or multi-dimensional queries?

Why it matters for bot defense

For bot-defense and CAPTCHA technology, understanding streaming quantile algorithms under turnstile models is valuable for real-time analysis of event distributions such as interaction timings, request latencies, or score histograms. The factorization-based framework offers a principled method to design space-efficient sketches that approximate linear queries on these streams with provable guarantees and low memory footprint. The improved correlation bounds and simplified single-sketch construction make implementations more practical and easier to reason about when deploying large-scale telemetry and anomaly detection. The strong lower bounds highlight fundamental limits, informing security engineers about tradeoffs between sketch size, query accuracy, and update flexibility—crucial for balancing cost-performance in live bot detection systems. Moreover, connections to differential privacy matrix mechanisms hint at potential cross-fertilization where approximate quantile computations can be done in a privacy-preserving manner while robustly handling adversarial updates. Overall, the matrix factorization approach sharpens the theoretical tools available for designing efficient streaming algorithms that underpin many background metrics and risk-scoring components in CAPTCHAs and bot-defense pipelines.

Cite

@article{arxiv2607_28819,
  title={ A Matrix Factorization Approach in Turnstile Streaming },
  author={ Jan Bulanek and Ravi Kumar and Raghu Meka and Jelani Nelson and Tamas Sarlos },
  journal={arXiv preprint arXiv:2607.28819},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.28819}
}

Read the full paper

• arXiv:2607.28819 (abstract)
• arXiv:2607.28819 (PDF)