Analysis of the Randomized Hadamard Transform

Abstract: This thesis is concerned with studying the use of structured random rotations of vectors, which can be implemented efficiently, as an approximation to impractical uniform random rotations in high dimensions. This is motivated by recent advances in data compression in Federated Learning applications where the volume of communication between nodes can be a major bottleneck. While there is some empirical evidence that such an approximation may work well, there is no theoretical justification. Our research question is therefore: is a structured rotation a good approximation for uniform rotation? If so, in what sense? An affirmative answer can serve as a theoretical justification for applying these rotations in practice. A negative answer however would suggest caution in applying these techniques. Our results are both positive and negative. On the positive side, we prove that the marginals of a vector rotated by the structured rotation converges in distribution to the marginals of a uniformly rotated one. On the negative side, we prove a lower bound on the Wasserstein distance between both distributions. The Wasserstein metric describes how far on average it is needed to move in order to transfer from one distribution to the other. To conclude, we found that there is some theoretical justification for the use of this approximation, however it is not perfect. Following this, we were able to describe what kind of error may be expected in the worst case. This allows for a better decision regarding the use of the structured rotation in each possible application.