# Improved Branch-and-Bound Antenna Selection Algorithm for Massive MIMO
## 3 Efficient Antenna Selection via Enhanced Branch-and-Bound Optimization
### Branch-and-Bound Antenna Selection
## Appendix A

### Theoretical Foundation of the Monotonicity Criterion

The monotonicity criterion: for any two antenna subsets \(\mathrm{H}_{1}\subseteq\mathrm{H}_{2}\), the channel capacity satisfies \(C_{1}\leq C_{2}\), let \(\mathbf{H}_{s}\) denote the submatrix obtained after antenna selection, then the channel capacity can be calculated as:

\[C=\log_{2}\det\!\left(\mathbf{I}_{N_{t}}+\frac{\rho}{N_{t}}\mathbf{H}^{\mathrm{ H}}\mathbf{H}\right), \tag{1}\]

If \(\mathrm{H}_{2}\) contains all rows of \(\mathrm{H}_{1}\) with an additional row, the inequality \(\det\!\left(\mathbf{H}_{2}^{\mathrm{H}}\mathbf{H}_{2}\right)\geq\det\!\left( \mathbf{H}_{1}^{\mathrm{H}}\mathbf{H}_{1}\right)\) holds, ensuring \(C_{1}\leq C_{2}\). This property is rigorously guaranteed by the positive definiteness of matrices [38] and the nested nature of determinants [39], independent of channel correlation. \(\square\)

### Monotonicity Analysis Under Correlated Channels

1. Correlated Channel Model: Assume the channel matrix \(\mathbf{H}\) follows a correlated Rayleigh fading model with covariance matrix \(\mathbf{R}=\mathbb{E}\!\left[\mathbf{H}^{\mathrm{H}}\mathbf{H}\right]\), decomposed as: \[\mathbf{H}=\mathbf{R}^{1/2}\mathbf{H}_{\mathrm{i.i.d.}},\] (2) where \(\mathbf{H}_{\mathrm{i.i.d. }}\) represents an independent and identically distributed (i.i.d.) channel matrix. 2. Impact of Correlation on Monotonicity: 1. Reduced Degrees of Freedom: High spatial correlation may decrease the rank of the channel matrix but does not violate the monotonicity of determinants. 2. Mathematical Proof: For any subsets \(\mathrm{H}_{1}\subseteq\mathrm{H}_{2}\), the correlated submatrices \(\mathrm{H}_{1}\) and \(\mathrm{H}_{2}\) satisfy: \[\det\!\left(\mathbf{I}+\mathbf{H}_{2}^{\mathrm{H}}\mathbf{H}_{2}\right)\geq \det\!\left(\mathbf{I}+\mathbf{H}_{1}^{\mathrm{H}}\mathbf{H}_{1}\right).\] (3) This conclusion derives directly from the Cauchy interlacing theorem for positive definite matrices [38], irrespective of channel independence. ## Appendix B

### Problem Definition and Assumptions

Consider a combinatorial optimization problem aiming to select a subset of elements that maximizes (or minimizes) a given objective function. The problem is assumed to satisfy the following properties:

1. Greedy Choice Property: A locally optimal choice at each step leads to a globally optimal solution. 2. Optimal Substructure: The optimal solution to the problem incorporates the optimal solutions to its subproblems. ### Related Definitions

1. Forward Selection: Starting from the initial state, this method iteratively selects the locally optimal solution at each step. Backward Path: Beginning at the target state (e.g., terminal point or final solution), this approach employs backward deduction to identify the locally optimal solution that induces the current state at each step. ### Theoretical Foundation

A matroid [40] is a mathematical structure defined by an axiomatic system of independent sets. Under the matroid framework, greedy algorithms are guaranteed to attain the global optimal solution. Specifically, if the feasible solution set of a problem forms a matroid, the optimality of the forward greedy algorithm is equivalent to that of the reverse deletion approach [41]. 1. Definition of Matroid: A matroid \(M=(S,\mathcal{P})\) satisfies: 1. Hereditary Property: If \(B\in\mathcal{P}\) and \(A\subseteq B\), then \(A\in\mathcal{P}\). 2. Exchange Property: If \(A,B\in\mathcal{P}\) and \(\left\lvert A\right\rvert<\left\lvert B\right\rvert\), then \(A\cup\left\lvert x\right\rvert\in\mathcal{P}\), \(x\in B\backslash A\). 2. Theorem (Optimality of Greedy Algorithm on Matroids): For the weight function \(w\): \(S\rightarrow\mathbb{R}^{+}\), the greedy algorithm that selects elements in descending order of weights yields the maximum-weight independent set (global optimal solution). Proof. : 1. Let \(G=\{g_{1},g_{2},\ldots,g_{k}\}\) denote the solution generated by the greedy algorithm, ordered in descending weights. 2.