Subspace embeddings with the rerandomized SRHT
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,⌈ Cr/ε2⌉}, for a universal constant C, suffices to preserve all squared norms on each fixed r-dimensional subspace within 1±ε 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.
Related
- A Near-Optimal Lower Bound for ℓp-Subspace Embeddings, 1≤ p<2
- Subspace concentration condition and Bogomolov--Gieseker inequality
- A proof of the Braun-Etzion-Vardy bound for binary subspace codes
- Discrete homotopy of graphs and k-parabolic subspace arrangements
- Bias-Corrected Subspace Intersection: Minimax-Optimal Shared Subspace Estimation in Multi-View Data
BibTeX
@misc{yang2026subspace,
title = {{Subspace embeddings with the rerandomized SRHT}},
author = {Yuning Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13946},
eprint = {2609.13946},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13946},
}
RIS
TY - UNPB
TI - Subspace embeddings with the rerandomized SRHT
AU - Yuning Yang
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.13946
UR - https://arxiv.org/abs/2609.13946
AB - 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,⌈ Cr/ε^2⌉}, for a universal constant C, suffices to preserve all squared norms on each fixed r-dimensional subspace within 1±ε 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.
ER -