Improved Subsampled Randomized Hadamard Transform for Linear SVM
  Subsampled Randomized Hadamard Transform (SRHT), a popular random projection
method that can efficiently project a $d$-dimensional data into $r$-dimensional
space ($r \ll d$) in $O(dlog(d))$ time, has been widely used to address the
challenge of high-dimensionality in machine learning. SRHT works by rotating
the input data matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ by Randomized
Walsh-Hadamard Transform followed with a subsequent uniform column sampling on
the rotated matrix. Despite the advantages of SRHT, one limitation of SRHT is
that it generates the new low-dimensional embedding without considering any
specific properties of a given dataset. Therefore, this data-independent random
projection method may result in inferior and unstable performance when used for
a particular machine learning task, e.g., classification. To overcome this
limitation, we analyze the effect of using SRHT for random projection in the
context of linear SVM classification. Based on our analysis, we propose
importance sampling and deterministic top-$r$ sampling to produce effective
low-dimensional embedding instead of uniform sampling SRHT. In addition, we
also proposed a new supervised non-uniform sampling method. Our experimental
results have demonstrated that our proposed methods can achieve higher
classification accuracies than SRHT and other random projection methods on six
real-life datasets.
