Row complexity of rerandomized Walsh subspace embeddings

Can two independent sign rerandomizations of the normalized Walsh transform, followed by uniform row sampling, embed a fixed d-dimensional real subspace of Rⁿ with only O(d/ε²) rows at fixed confidence? Here n is a power of two.

Why it matters and what counts as progress

Why it matters: Removing logarithmic row overhead strengthens a structured alternative to dense random subspace embeddings.

What counts as progress: A uniform squared-norm guarantee with probability at least 1−δ and an explicit row count, retaining the confidence dependence rather than treating it as a constant.

How the problem developed

5 Feb 2026 · Open question [1]
Simons Institute workshop participants Asked whether rerandomized subsampled trigonometric transforms can embed an r-dimensional subspace using O(r/ε²) sampled rows.
18 Oct 2026 · Theorem [2]
Diar Heidary For a fixed orthonormal frame and fixed failure probability, proved an O(d/ε²) row bound for a rerandomized Walsh transform followed by uniform row sampling.

AI contribution

AI-assisted Walsh embedding reaches linear row scaling

For n=2^k, a fixed real orthonormal n×d frame, 0<ε<1 and 0<δ<1/2, two independent sign rerandomizations of the normalized Walsh transform followed by uniform row sampling preserve all squared norms within ε with probability at least 1−δ. The stated row count is min(n,⌈8192(d+27⌈log₄(4d/δ)⌉³)/ε²⌉), which is O(d/ε²) for fixed δ.

AI involvementAI-centered

ImportanceNotable

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

Human understandingFew