Large-Scale Kernel-Based Feature Extraction via Low-Rank Subspace Tracking on a Budget

Fatemeh Sheikholeslami, Dimitris Berberidis, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Kernel-based methods enjoy powerful generalization capabilities in learning a variety of pattern recognition tasks. When such methods are provided with sufficient training data, broadly applicable classes of nonlinear functions can be approximated with desired accuracy. Nevertheless, inherent to the nonparametric nature of kernel-based estimators are computational and memory requirements that become prohibitive with large-scale datasets. In response to this formidable challenge, this paper puts forward a low-rank, kernel-based, feature extraction approach that is particularly tailored for online operation. A novel generative model is introduced to approximate high-dimensional (possibly infinite) features via a low-rank nonlinear subspace, the learning of which lends itself to a kernel function approximation. Offline and online solvers are developed for the subspace learning task, along with affordable versions, in which the number of stored data vectors is confined to a predefined budget. Analytical results provide performance bounds on how well the kernel matrix as well as kernel-based classification and regression tasks can be approximated by leveraging budgeted online subspace learning and feature extraction schemes. Tests on synthetic and real datasets demonstrate and benchmark the efficiency of the proposed method for dynamic nonlinear subspace tracking as well as online classification and regressions tasks.

Original languageEnglish (US)
Pages (from-to)1967-1981
Number of pages15
JournalIEEE Transactions on Signal Processing
Issue number8
StatePublished - Apr 15 2018

Bibliographical note

Funding Information:
Manuscript received May 12, 2017; revised November 14, 2017 and December 20, 2017; accepted January 21, 2018. Date of publication February 5, 2018; date of current version March 1, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Wenwu Wang. This work was supported in part by the NSF under Grants 1500713 and 1514056 and in part by the NIH under Grant 1R01GM104975-01. This paper was presented in part at the IEEE Global Conference on Signal and Information Processing, Orlando, FL, USA, December 2015 and in part at the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Curacao, Dutch Antilles, December 2017. (Corresponding author: Georgios B. Giannakis.) The authors are with the Department of Electrical and Computer Engineering and the Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA (e-mail:;; georgios@

Publisher Copyright:
© 1991-2012 IEEE.


  • Online nonlinear feature extraction
  • budgeted learning
  • classification
  • kernel methods
  • nonlinear subspace tracking
  • regression


Dive into the research topics of 'Large-Scale Kernel-Based Feature Extraction via Low-Rank Subspace Tracking on a Budget'. Together they form a unique fingerprint.

Cite this