Incremental regularized least squares for dimensionality reduction of large-scale data

Xiaowei Zhang, Li Cheng, Delin Chu, Li Zhi Liao, Michael K. Ng, Roger C. E. Tan

Research output: Contribution to journalJournal articlepeer-review

6 Citations (Scopus)
27 Downloads (Pure)


Over the past few decades, much attention has been drawn to large-scale incremental data analysis, where researchers are faced with huge amounts of high-dimensional data acquired incrementally. In such a case, conventional algorithms that compute the result from scratch whenever a new sample comes are highly inefficient. To conquer this problem, we propose a new incremental algorithm incremental regularized least squares (IRLS) that incrementally computes the solution to the regularized least squares (RLS) problem with multiple columns on the right-hand side. More specifically, for an RLS problem with c (c > 1) columns on the right-hand side, we update its unique solution by solving an RLS problem with a single column on the right-hand side whenever a new sample arrives, instead of solving an RLS problem with c columns on the right-hand side from scratch. As a direct application of IRLS, we consider the supervised dimensionality reduction of large-scale data and focus on linear discriminant analysis (LDA). We first propose a new batch LDA model that is closely related to the RLS problem, and then apply IRLS to develop a new incremental LDA algorithm. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of our algorithms.

Original languageEnglish
Pages (from-to)B414-B439
Number of pages26
JournalSIAM Journal on Scientific Computing
Issue number3
Publication statusPublished - 25 May 2016

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Incremental regularized least squares
  • Linear discriminant analysis
  • Lsqr
  • Supervised dimensionality reduction


Dive into the research topics of 'Incremental regularized least squares for dimensionality reduction of large-scale data'. Together they form a unique fingerprint.

Cite this