Subset selection in sparse matrices
This addresses computational bottlenecks in variable selection for sparse data, though it appears incremental as it builds on known complexity results.
The paper tackles the NP-hard subset selection problem for linear predictors by showing that certain sparsity conditions on the data matrix enable polynomial-time solutions, using tools from discrete geometry.
In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow us to solve the problem in polynomial time.