Self basis selection in a finite set

Our work on basis selection is motivated by a sensor selection problem for interference cancellation in digital communication. Given a set of n vectors in R^m we wish to find a subset of m vectors that are good "predictors" for the complementary set. We consider two criteria of goodness, one leads to requiring that the least-squares expansion coefficients of the complementary set be bounded by one, the other leads to maximizing the determinant of the selected subset. Exhaustive search requires checking all n choose m possible subsets. We present a low-complexity iterative selection algorithm, and examine its worst loss with respect to the optimum solution under both goodness criteria. We show that with linear complexity in n the proposed algorithm achieves the bounded coefficients criterion, while the determinant of the selected set is at most m^m2/ below the true maximum determinant.