Sparsity and row bounds for independent SparseStack embeddings

Can a fully independent signed-hash SparseStack matrix preserve the norms of a fixed d-dimensional real subspace with row count O((d+log(d/δ))/ε²) and column sparsity O(log(d/δ)/ε)?

Why it matters and what counts as progress

Why it matters: The target combines low embedding dimension with fast sparse matrix application.

What counts as progress: A failure-probability bound at most δ with explicit row and sparsity constants for the stated independent construction, or a stronger guarantee under weaker randomness.

How the problem developed

2013 · Conjecture [1]
Kane and Nelson Nelson and Nguyen proposed optimal row and sparsity scales for SparseStack oblivious subspace embeddings under full independence.
30 Jun 2025 · Partial result [2]
Shabarish Chenakkod, Michał Dereziński and Xiaoyu Dong Published optimal row-count embeddings with sparsity near-optimal up to subpolynomial factors, leaving the conjectured sparsity scale unresolved.
9 Sept 2026 · Proof [3]
Diar Heidary Proved the conjectured row and nonzero-per-column bounds for fully independent SparseStack on any fixed d-dimensional subspace, with explicit constants and a Lean-verified main theorem.

AI contribution

A Sparse-Fock Proof of the Upper Edge for Fully Independent SparseStack

Diar Heidary

For a fixed n×d real matrix U with UᵀU=I, d≥1, 0<ε≤1 and 0<δ≤1, the fully independent signed-hash SparseStack construction gives failure probability at most δ with column sparsity below 1356 max(1,⌈log₂(d/δ)⌉)/ε and row count below 306456(d+max(1,⌈log₂(d/δ)⌉))/ε².

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (Lean 4/Mathlib kernel, Comparator and NanoDa)

Human understandingFull