Hadamard Transforms for Dimension Reduction

@misc{sun2026hadamard,
  title = {{Hadamard Transforms for Dimension Reduction}},
  author = {Mingxuan Sun and Zhiqiang Xu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.25762},
  eprint = {2610.25762},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.25762},
}

TY  - UNPB
TI  - Hadamard Transforms for Dimension Reduction
AU  - Mingxuan Sun
AU  - Zhiqiang Xu
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.25762
UR  - https://arxiv.org/abs/2610.25762
AB  - Using the Hadamard matrix for dimension reduction can accelerate the computation due to the fast Hadamard transform. However, the previous target dimension bounds in terms of the Gaussian width depend on the ambient dimension. In this paper, we obtain the following ambient dimension free bound using three Hadamard-diagonal blocks. Let H∈ℝ^d× d be the normalized Walsh-Hadamard matrix, and let D_1,D_2,D_3∈ℝ^d× d be independent Rademacher diagonal matrices. We prove that for any symmetric set T⊂ 𝕊^d−1, ℙ{sup_t∈ T|d/m|P_ΩHD_3HD_2HD_1t|_2^2−1|≤ε} ≥1−δ whenever m≳ε^−2w(T)^2log^2e/δ log^4 (e+w(T)/εloge/δ). Here w(T) is the Gaussian width of T, and Ω is a set of m distinct coordinates chosen uniformly. This is the first ambient dimension free bound on the target dimension using Hadamard transforms, for an arbitrary symmetric set in terms of its Gaussian width. We also prove that it is impossible to obtain an ambient dimension free bound for an arbitrary set in terms of its Gaussian width using two Hadamard-diagonal blocks.
ER  -