Subspace embeddings with the rerandomized SRHT
TL;DR
Subspace embeddings obtained by two normalized real Walsh transforms, two independent sign diagonals, and uniform coordinate sampling without replacement suffices to preserve all squared norms on each fixed $r$-dimensional subspace within $1\pm\varepsilon$ with probability at least $0.99".
Abstract
This work studies subspace embeddings obtained by two normalized real Walsh transforms, two independent sign diagonals, and uniform coordinate sampling without replacement. The main result shows that the prescribed sample size $k=\min\{n,\lceil Cr/\varepsilon^2\rceil\}$, for a universal constant $C$, suffices to preserve all squared norms on each fixed $r$-dimensional subspace within $1\pm\varepsilon$ with probability at least $0.99$. The result holds for every ambient Walsh dimension and all ranks, and answers Problem TR-01 in the Open Problems in Numerical Linear Algebra repository. The proof controls joint entry cumulants of the transformed projection through connected graph contractions and Walsh character identities. These estimates then bound the expected trace of even powers of a product of centered projections. A two-projection decomposition converts this estimate into control of both spectral edges. Bernoulli sampling at arbitrary densities and a deterministic upper bound near full sampling yield the prescribed number of coordinates.