Sparsity of one-sided subspace embeddings

A random sketch compresses vectors into fewer dimensions. A one-sided subspace embedding must keep every direction in a fixed subspace from collapsing. It can expand lengths.

Why it matters and what counts as progress

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

What counts as progress: Bounds should specify the subspace dimension, sketch size, allowed entries per row, success probability and any structural restrictions on the sketch.

How the problem developed

  1. August 2025 · Development [1]

    SparseStack authors Introduced the structured random sketch and raised the sparsity question for one-sided guarantees.

  2. 9 Nov 2026 · Proof [2][3][4]

    Lorenzo Beretta and colleagues Gave an O(log⁡r)O(\sqrt{\log r}) construction at linear dimension and a nearly matching lower bound for overlap-restricted sketches.

AI contribution

Optimal Injectivity of the SparseStack

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.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean + human)
Human understandingFew
Paper date:

Sources

  1. Earlier SparseStack construction and one-sided question
  2. Original manuscript
  3. AI disclosure and author checks
  4. Lean development and stated scope
Publication history