Improved subsampled randomized hadamard transform for linear SVM

Zijian Lei, Liang Lan

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

2 Citations (Scopus)


Subsampled Randomized Hadamard Transform (SRHT), a popular random projection method that can efficiently project a d-dimensional data into r-dimensional space (r≤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 X ∈Rn×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.

Original languageEnglish
Title of host publicationAAAI 2020 - 34th AAAI Conference on Artificial Intelligence
PublisherAAAI press
Number of pages8
ISBN (Electronic)9781577358350
Publication statusPublished - 3 Apr 2020
Event34th AAAI Conference on Artificial Intelligence, AAAI 2020 - New York, United States
Duration: 7 Feb 202012 Feb 2020

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


Conference34th AAAI Conference on Artificial Intelligence, AAAI 2020
Country/TerritoryUnited States
CityNew York
Internet address

Scopus Subject Areas

  • Artificial Intelligence


Dive into the research topics of 'Improved subsampled randomized hadamard transform for linear SVM'. Together they form a unique fingerprint.

Cite this