Numerical investigation of a continuous relaxation for the column subset selection problem

Details

Supervisors

Massart, Estelle

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

This thesis presents a novel approach to approximating the Column Subset Selection Problem (CSSP) using a regularized continuous optimization method. The CSSP, which involves selecting a subset of columns from a given matrix to best approximate the original matrix, is a combinatorial problem that is NP-hard. This thesis introduces a method that transforms the combinatorial problem into a continuous optimization task by employing an \(L_1\) orthogonal regularization term. The proposed method is particularly well-suited for datasets where the number of features significantly exceeds the number of objects (m << n). The thesis includes a comprehensive analysis of the algorithm's performance against existing methods. Results from experiments on both synthetic and real-world datasets demonstrate that the proposed method offers competitive precision and computational efficiency compared to existing methods. Its effectiveness in scenarios where the number of features far exceeds the number of objects (m << n) makes it a viable solution for large-scale applications.