The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


Subset selection with sparse matrices

Alberto Del Pia,

Date and Time: Mar 14, 2018 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


In subset selection we search for the best linear predictor that involves a small subset of variables. Due to the vast applicability of this model, many approaches have been proposed by different communities, including enumeration, greedy algorithms, branch and bound, and convex relaxations. Our point of departure is to understand the problem from a computational complexity viewpoint. Using mainly tools from discrete geometry, we show that the problem can be solved in polynomial time if the associated data matrix is obtained by adding a fixed number of columns to a block diagonal matrix. This is joint work with Santanu S. Dey and Robert Weismantel.