RT Journal Article
SR 00
ID 10.1016/j.ins.2019.02.039
A1 Ordozgoiti Rubio, Bruno
A1 Mozo Velasco, Bonifacio Alberto
A1 Garcia Lopez De Lacalle, Jesus
T1 Regularized greedy column subset selection
JF Information Sciences
YR 2019
FD 2019-06
VO 486
SP 393
OP 418
K1 Feature selection; Column subset selection; Unsupervised learning
AB 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.
PB Elsevier
SN 0020-0255
LK https://oa.upm.es/64356/
UL https://www.sciencedirect.com/science/article/abs/pii/S0020025519301495