Hadamard transforms reduce dimension without depending on original size
Hadamard Transforms for Dimension Reduction
Data Structures and Algorithms
Summary
Dimension reduction helps simplify large data by shrinking its size while keeping important information. The authors show a new way to use Hadamard transforms that speeds up this process and removes the usual need to consider the original data’s size. They prove this method works well for a broad group of data types defined by something called Gaussian width. They also show that using fewer steps won’t achieve this independence from data size.
What this means in practice
- •For machine learning engineers: Design dimension reduction steps for algorithms that do not require knowing the original data size when working with structured random transforms.
- •For signal processing developers: Develop faster dimension reduction pipelines that maintain accuracy for signals represented in high-dimensional spaces by using three Hadamard-diagonal blocks.
A theory result. No direct application yet.
Authors
Mingxuan Sun, Zhiqiang Xu
Abstract
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\in\mathbb R^{d\times d}$ be the normalized Walsh-Hadamard matrix, and let $D_1,D_2,D_3\in\mathbb R^{d\times d}$ be independent Rademacher diagonal matrices. We prove that for any symmetric set $T\subset \mathbb{S}^{d-1}$, \[ \mathbb P\left\{\sup_{\boldsymbol t\in T}\big|\frac dm\|P_ΩHD_3HD_2HD_1\boldsymbol t\|_2^2-1\big|\le\varepsilon\right\} \ge1-δ\] whenever \[ m\gtrsim\varepsilon^{-2}w(T)^2\log^2\frac eδ\,\log^4\!\left(e+\frac{w(T)}\varepsilon\log\frac eδ\right). \] 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.