A Near-Optimal Lower Bound for Prefix-Matrix Factorizations

Abstract

For the $n\times n$ lower-triangular all-ones matrix $Q$, we prove a near-optimal lower bound \[ γ_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = Ω\!\left( \frac{\log^{3/2}n}{(\log\log n)^{3/2}} \right), \] where the infimum ranges over real factorizations of arbitrary finite inner dimension. This cost is a central parameter in space bounds for factorization-based rank and quantile estimation in turnstile streams and in error bounds for matrix mechanisms for continual counting under pure differential privacy. The proof combines right-sided Haar projections with a scale-dependent numerical-sparsity decomposition of the rows of $B$. At each scale, a rank--Frobenius argument shows that the numerically sparse rows cannot account for all of the required Schatten $2/3$ mass, while a Haar projection estimate bounds the contribution of the remaining rows. Summing these bounds over the dyadic scales yields the result. The proof was obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors verified the proof and made minor revisions.