A fast and optimal deterministic algorithm for NP-Hard antenna selection problem

Existing fast antenna selection algorithms have either low performance gains or they are efficient only for the selection of particular size sub-matrices. Our motivation to the study of NP-Hard antenna selection problem is two-fold. First, we intend to propose an optimal algorithm that is equally efficient for each possible subset cardinality of the transmit and/or receive antennas. Second, different from any of the antenna selection algorithms proposed so far, our algorithm deterministically increases the strength of the singular values during the selection of each column of the selected matrix. This increase in the singular values is defined by a very tight bound. This bound has previously been used to analyze the efficiency of low rank approximation algorithms. Hence, our antenna selection procedure is as efficient as that of a best algorithm for matrix low rank approximations.