Hadamard Transforms for Dimension Reduction

Source 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.