Optimal dimension for a rerandomized Hadamard embedding
Let $n$ be a power of two and $1 \le k \le n$. Let $F$ be the $n \times n$ Walsh–Hadamard matrix scaled by $n^{-1/2}$, so that it is orthogonal; let $D_1, D_2$ be diagonal matrices with independent Rademacher diagonal entries; and let $S \in \mathbb{R}^{n \times k}$ have as columns the coordinate vectors $e_j$, $j \in J$, of a uniformly random $k$-element set $J \subseteq \{1, \dots, n\}$, with $D_1$, $D_2$ and $S$ independent. Amsel et al. call $$\Omega = \sqrt{n/k}\, D_1 F D_2 F S$$ a rerandomized subsampled randomized Hadamard transform (SRHT). For the SRHT with one randomization, $\Omega_1 = \sqrt{n/k}\, D_1 F S$, Tropp proved that if $k \ge 4\bigl(\sqrt{r} + \sqrt{8 \log(rn)}\bigr)^2 \log r$, then for every $r$-dimensional subspace $V \subseteq \mathbb{R}^n$, except with probability at most $3/r$, $\|x\|_2^2/6 \le \|\Omega_1^{\mathsf T} x\|_2^2 \le 13\|x\|_2^2/6$ for every $x \in V$; he gave an example, from Halko, Martinsson and Tropp, with $n = r^2$ showing that the factor $\log r$ cannot be removed in general.
Problem. Is there a universal constant $C > 0$ such that, for every power of two $n$, every $1 \le r \le n$, every $0 < \varepsilon < 1/2$ and every $r$-dimensional subspace $V \subseteq \mathbb{R}^n$, taking $k = \min\{n, \lceil Cr/\varepsilon^2 \rceil\}$ gives $$\Pr\bigl\{(1 - \varepsilon)\|x\|_2^2 \le \|\Omega^{\mathsf T} x\|_2^2 \le (1 + \varepsilon)\|x\|_2^2 \text{ for every } x \in V\bigr\} \ge 0.99?$$
Source: Stated by OpenProblemsInNLA, after Amsel et al. (2026), Problem 5.6, which asks whether the rerandomized SRHT with k = O(r/ε²) is an oblivious subspace embedding with distortion 1 ± ε.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- OpenProblemsInNLA, randomized Hadamard transforms, sketching, subspace embeddings
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
}
@article{tropp2011,
author = {Tropp, Joel A.},
title = {Improved analysis of the subsampled randomized {H}adamard transform},
journal = {Adv. Adapt. Data Anal.},
volume = {3},
number = {1--2},
year = {2011},
pages = {115--126},
doi = {10.1142/S1793536911000787},
eprint = {1011.1595},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-tr01,
author = {Townsend, Alex},
title = {{TR-01}: Optimal dimension for a rerandomized Hadamard embedding},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/TR-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00206, "Optimal dimension for a rerandomized Hadamard embedding", clopen.solutions.