Title: Regularized Greedy Column Subset Selection,
Abstract: The Column Subset Selection Problem provides a natural framework for
unsupervised feature selection. Despite being a hard combinatorial optimization
problem, 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.