Optimal Injectivity of the SparseStack

Get email updates

Lorenzo Beretta, Simone Bombari, Margalit Glasgow, Raphael Arkady Meyer, Kijun Shin, David P. Woodruff

SparseStack can sketch to Θ(r)\Theta (r) dimensions using O(log⁡r)O(\sqrt{\log r}) nonzero entries per row and keeps the smallest singular value bounded below on each fixed r-dimensional subspace with constant success probability. A separate lower bound needs Ω((log⁡r/log⁡log⁡r))\Omega (\sqrt{(\log r/\log \log r)}) nonzeros per row for isotropic sketches satisfying the paper’s row-support overlap condition.

What was already known

Two-sided length preservation needs order log⁡r\log r row sparsity at linear embedding dimension. Earlier one-sided lower bounds ruled out constant sparsity under additional structural assumptions.

AI involvement AI-led

The authors credit the Gemini 4 Colosseum harness with most technical proofs and derivations. They independently proved several structural lemmas, edited the presentation and checked the mathematical steps.

Importance Notable

The construction shows that preventing collapse alone permits substantially sparser sketches at the same embedding dimension.

Technical verification Formal (Lean + human)

The authors report checking the mathematical arguments and auditing the correspondence between the Lean statements and both results.

Independent checking

Checked the mathematical steps and audited the formal definitions and theorem statements.

Checker
Paper authors
Scope
SparseStack can sketch to Θ(r)\Theta (r) dimensions using O(log⁡r)O(\sqrt{\log r}) nonzero entries per row and keeps the smallest singular value bounded below on each fixed r-dimensional subspace with constant success probability. A separate lower bound needs Ω((log⁡r/log⁡log⁡r))\Omega (\sqrt{(\log r/\log \log r)}) nonzeros per row for isotropic sketches satisfying the paper’s row-support overlap condition.
Basis
Reported by the linked checker

Formal checking

Checked the upper and lower bounds in the published Lean development.

Checker
Lean 4 kernel
Scope
SparseStack can sketch to Θ(r)\Theta (r) dimensions using O(log⁡r)O(\sqrt{\log r}) nonzero entries per row and keeps the smallest singular value bounded below on each fixed r-dimensional subspace with constant success probability. A separate lower bound needs Ω((log⁡r/log⁡log⁡r))\Omega (\sqrt{(\log r/\log \log r)}) nonzeros per row for isotropic sketches satisfying the paper’s row-support overlap condition.
Basis
Reported by the linked checker

Human understanding Few

The disclosure records author contributions and checking. A human account of the model-generated parts of the proof is undocumented.

Other useful sources

Correction and publication history