Sub-Modularity and Antenna Selection in MIMO Systems

In this paper, we show that the optimal receive antenna subset selection problem for maximizing the mutual information in a point-to-point MIMO system is sub-modular. Consequently, a greedy step-wise optimization approach, where at each step, an antenna that maximizes the incremental gain is added to the existing antenna subset, is guaranteed to be within a (1-1/e)-fraction of the global optimal value independent of all parameters. For a single-antenna-equipped source and destination with multiple relays, we show that the relay antenna selection problem to maximize the mutual information is modular and a greedy step-wise optimization approach leads to an optimal solution.