Regularized greedy column subset selection

Ordozgoiti Rubio, Bruno and Mozo Velasco, Bonifacio Alberto and Garcia Lopez De Lacalle, Jesus (2019). Regularized greedy column subset selection. "Information Sciences", v. 486 ; pp. 393-418. ISSN 0020-0255.


Title: Regularized greedy column subset selection
  • Ordozgoiti Rubio, Bruno
  • Mozo Velasco, Bonifacio Alberto
  • Garcia Lopez De Lacalle, Jesus
Item Type: Article
Título de Revista/Publicación: Information Sciences
Date: June 2019
ISSN: 0020-0255
Volume: 486
Freetext Keywords: Feature selection; Column subset selection; Unsupervised learning
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (9MB) | Preview


The Column Subset Selection Problem is a hard combinatorial optimization problem that provides a natural framework for unsupervised feature selection, and there exist efficient algorithms that provide good approximations. The drawback of the problem formulation is that it incorporates no form of regularization, and is therefore very sensitive to noise when presented with scarce data. In this paper we propose a regularized formulation of this problem, and derive a correct greedy algorithm that is similar in efficiency to existing greedy methods for the unregularized problem. We study its adequacy for feature selection and propose suitable formulations. Additionally, we derive a lower bound for the error of the proposed problems. Through various numerical experiments on real and synthetic data, we demonstrate the significantly increased robustness and stability of our method, as well as the improved conditioning of its output, all while remaining efficient for practical use.

More information

Item ID: 64356
DC Identifier:
OAI Identifier:
DOI: 10.1016/j.ins.2019.02.039
Official URL:
Deposited by: Memoria Investigacion
Deposited on: 18 Jan 2021 12:47
Last Modified: 18 Jan 2021 14:52
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM