Subset selection with sparse matrices

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.

https://vimeo.com/260483510