A Bidirectional Greedy Heuristic for the Subspace Selection Problem
The Subspace Selection Problem (SSP) amounts to selecting t out of n given vectors of dimension m, such that they span a subspace in which a given target b Rm has a closest possible approximation. This model has numerous applications in e.g. signal compression and statistical regression. It is well known that the problem is NP hard. Based on elements from a forward and a backward greedy method, we develop a randomized search heuristic, which in some sense resembles variable neighborhood search, for SSP. Through numerical experiments we demonstrate that this approach has good promise, as it produces good results at modest computational cost.
SLS