2012 · 57 citations · 11 references
ComputingComputer ScienceAlgorithmsMachine LearningTime Series AnalysisDigital Signal ProcessingKernel MethodsOnline AlgorithmsOptimization For Machine LearningPattern RecognitionSignal ProcessingComputational Complexity Of AlgorithmsKernel ApproximationKernel LearningLearning KernelsOnline Machine LearningReal-time ProcessingReal-time Signal Processing
Online kernel algorithms have an important computational drawback. The computational complexity of these algorithms grow linearly over time. This makes these algorithms difficult to use for real time signal processing applications that need to continuously process data over prolonged periods of time. In this paper, we present a way of overcoming this problem. We do so by approximating kernel evaluations using finite dimensional inner products in a randomized feature space. We apply this idea to the Kernel Least Mean Square (KLMS) algorithm, that has recently been proposed as a non-linear extension to the famed LMS algorithm. Our simulations show that using the proposed method, constant computational complexity can be achieved, with no observable loss in performance.
11
UCI Machine Learning Repository
Arthur Asuncion · Medical Entomology and Zoology · 2007 · 24.4K citations
Steven C. Rogers · Control Engineering Practice · 1996 · 9.3K citations
Random Features for Large-Scale Kernel Machines
Ali Rahimi, Benjamin Recht · 2007 · 2.7K citations
Pegasos: primal estimated sub-gradient solver for SVM
Shai Shalev‐Shwartz, Yoram Singer, Nathan Srebro et al. · Mathematical Programming · 2010 · 1.5K citations
Jyrki Kivinen, Alex Smola, Robert C. Williamson · IEEE Transactions on Signal Processing · 2004 · 1K citations