Online kernel methods suffer from computational and memory complexity in large-scale problems. Due to these drawbacks, budget online kernel learning and kernel approximation (low-dimensional feature map approximation) methods are widely used to speed up time and to reduce memory usage of kernel approaches. In this paper, orthogonal Gram-Schmidt explicit feature maps are applied to online kernel methods. The main advantage of these feature maps come from their orthogonality property. Utilization of these feature maps leads to mutually linearly independent dimensions of feature space, hence, reduce the redundancy in this space. These feature maps can be applied to single-pass online learning methods with $l_2$- and $l_0$-norm regularization to reduce the computational and memory complexity. In this paper, the proposed methods are named: 1) Online Feature Maps (OFEMs) and 2) Sparse Online Feature Maps (SOFEMs). These methods are examined for binary and multiclass single-label classification problems. Extensive experiments are compared with the results of other state-of-the-art methods on standard and real-world datasets. The experimental results show that OFEMs and SOFEMs outperform other methods in the literature.

Keywords