Abstract
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. 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, when complete channel state information is available at the relays. As a result a greedy step-wise optimization approach leads to an optimal solution for the relay antenna selection problem with linear complexity in comparison to the brute force search that incurs exponential complexity.
Introduction
Multiple-Input Multiple-Output (MIMO) technology is a cornerstone of modern wireless communication, enabling high data rates and increased reliability through spatial multiplexing and diversity. However, the practical implementation of MIMO systems is often constrained by the high cost and power consumption of Radio Frequency (RF) chains, including power amplifiers and analog-to-digital converters.
Antenna selection offers a pragmatic solution: by selecting a subset of $L$ antennas from a larger set of $N$ available elements, engineers can capture a significant portion of the MIMO capacity while utilizing fewer RF chains. The primary challenge lies in the selection process itself. Finding the mathematically optimal subset typically requires an exhaustive brute-force search, which scales exponentially as $O\binom{N}{L}$. This "curse of dimensionality" makes optimal selection infeasible for real-time systems or Massive MIMO deployments. While greedy heuristics—which select antennas one-by-one based on immediate gain—have been used in practice, their theoretical reliability remained unproven until this work.
The Sub-modularity Framework
This research bridges the gap between wireless communications and combinatorial optimization by leveraging the concept of sub-modularity. In discrete optimization, a function is sub-modular if it satisfies the law of diminishing returns: the marginal gain of adding an element to a set decreases as the set size increases.
Formally, for a set function $f$, if $A \subseteq B$, then for any element $e \notin B$: $$f(A \cup \{e\}) - f(A) \geq f(B \cup \{e\}) - f(B)$$
Theoretical Proofs
The authors provide two rigorous proofs to demonstrate that receive antenna selection in a point-to-point MIMO system is sub-modular:
- Information Theoretic Approach: They map the mutual information of the MIMO system to the entropy of a Gaussian random vector, which is a known sub-modular function.
- Matrix Theory Approach: Using the properties of determinants and the physics of Multiple Access Channels (MAC), they demonstrate that the incremental capacity gain of an additional antenna is always higher when added to a smaller subset than a larger one.
Performance Guarantees
By establishing that the objective function is sub-modular and monotone, the authors invoke a classic result from optimization theory: a greedy algorithm is guaranteed to achieve at least $(1 - 1/e) \approx 63.2\%$ of the global optimum.
In the specific case of relay antenna selection (where a single-antenna source and destination communicate via multiple Amplify-and-Forward relays), the problem is shown to be modular. In a modular problem, the contribution of each element is independent. This is a significant finding because it implies that for relay networks, the greedy algorithm is not just an approximation—it is mathematically guaranteed to find the global optimum with linear complexity $O(LN)$.
The Transmit Selection Exception
An important nuance identified in the paper is that transmit antenna selection is not sub-modular. This discrepancy arises from the equal power splitting rule. In a receiver, adding an antenna increases the total captured energy. However, in a transmitter with a fixed power budget, adding an antenna requires splitting the existing power across more elements. This dilution of power per antenna can, in some channel conditions, lead to a decrease in total mutual information, violating the monotonicity required for sub-modular guarantees.
Results and Complexity
The shift from brute-force to greedy optimization represents a massive reduction in computational overhead, moving from exponential complexity to linear complexity ($O(L \cdot N)$).
To validate the theoretical bounds, the authors conducted Monte Carlo simulations using Rayleigh fading channel models. The results indicated that while the theoretical "floor" is 63.2%, the greedy algorithm's actual performance in standard MIMO configurations is nearly indistinguishable from the brute-force optimal solution. In the relay scenario, the greedy algorithm consistently achieved 100% of the optimal capacity, confirming the modularity proof.
Conclusion and Future Work
This work provides the first rigorous theoretical foundation for the use of greedy algorithms in MIMO antenna selection. By proving sub-modularity for receivers and modularity for relays, it justifies the use of low-complexity selection methods in practical hardware.
Future research directions include:
- Transmitter CSI: Investigating how sub-modularity changes when the transmitter has Channel State Information and employs water-filling power allocation.
- Transmit Selection Theory: Developing new theoretical frameworks to bound performance for the transmit side, where sub-modularity does not hold.
- Multi-user Scenarios: Extending these proofs to multi-antenna relays and interference-limited multi-user channels.
Summary updated