Compact Random Feature Maps
Roszilah Hamid, Ying Xiao, Alex Gittens, Dennis DeCoste · 2014
Kernel approximation using random feature maps has recently gained a lot of interest. This is mainly due to their applications in reducing train-ing and testing times of kernel based learning al-gorithms. In this work, we identify that previous approaches for polynomial kernel approximation create maps that can be rank deficient, and there-fore may not utilize the capacity of the projected feature space effectively. To address this chal-lenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial ker-nels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrat-ing their superior kernel reconstruction perfor-mance compared to the previous approxima-tion schemes. We show how structured ran-dom matrices can be used to efficiently gener-ate CRAFTMaps, and present a single-pass al-gorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results. 1.