Hadamard Transforms for Dimension Reduction
En palabras de los autores
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.
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.