Uniform Approximations for Randomized Hadamard Transforms with Applications

Understand

Randomized Hadamard Transforms (RHTs) have emerged as a computationally efficient alternative to the use of dense unstructured random matrices across a range of domains in computer science and machine learning.

• For several applications such as dimensionality reduction and compressed sensing, the theoretical guarantees for methods based on RHTs are comparable to approaches using dense random matrices with i.i.d.\ entries.
• However, several such applications are in the low-dimensional regime where the number of rows sampled from the matrix is rather small.
• Prior arguments are not applicable to the high-dimensional regime often found in machine learning applications like kernel approximation.