pipette
ESEspañol

Hadamard Transforms for Dimension Reduction

Mingxuan Sun, Zhiqiang Xu

Preprint

In the authors' words

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 be the normalized Walsh-Hadamard matrix, and let be independent Rademacher diagonal matrices. We prove that for any symmetric set , \[ \mathbb P\left\{\sup_{\boldsymbol t\in T}\big|\frac dm\|P_\Omega HD_3HD_2HD_1\boldsymbol t\|_2^2-1\big|\le\varepsilon\right\} \ge1-\delta \] whenever \[ m\gtrsim\varepsilon^{-2}w(T)^2\log^2\frac e\delta \log^4\!\left(e+\frac{w(T)}\varepsilon\log\frac e\delta\right). \] Here is the Gaussian width of , and is a set of 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.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.