## 3 Decremental Antenna Selection Algorithms
### Modified Random Decremental Selection (MRDS)  
To improve the efficiency of the RDS algorithm, we further propose the modified random decremental selection (MRDS) algorithm through introducing an effective and accurate approximation of the minimal transmit power consumption based on the asymptotic orthogonality of the channels [11]. The asymptotic orthogonality reduces the complexity of signal processing. To maximize the minimum SINR of all the users constrained by the transmit power, [PERSON] _et al._ proved that the asymptotically optimal beamformer when \(N\rightarrow\infty\) is a linear combination of the channels between the BS and its served users [12].  
**Theorem 2**: _To minimize the transmit power constrained by the SNR requirement, the optimal beamforming vector is a linear combination of user' channels if they are orthogonal, that is \(\mathbf{w}^{\mathrm{opt}}=\sum_{i=1}^{M}\alpha_{i}\mathbf{h}_{i}\), where \(\alpha_{i}\) is the coefficient of user \(i\) in the combination._  
Let \(\{\mathbf{u}_{j}\}_{j=1}^{N-M}\) be an orthogonal basis for the complement of the space spanned by \(\{\mathbf{h}_{i}\}_{i=1}^{M}\), then  
\[\mathbf{w}=\sum_{i=1}^{M}\alpha_{i}\mathbf{h}_{i}+\sum_{j=1}^{M-N}\xi_{j} \mathbf{u}_{j} \tag{5}\]  
Let \(\mathbf{v}=\sum_{i=1}^{M}\alpha_{i}\mathbf{h}_{i}\). We can observe that if \(\mathbf{w}\) satisfies the constrains, \(\mathbf{v}\) also satisfies, and \(\|\mathbf{w}\|_{2}^{2}\geq\|\mathbf{v}\|_{2}^{2}\) due to the orthogonality of \(\{\mathbf{u}_{j}\}_{j=1}^{N-M}\) and \(\{\mathbf{h}_{i}\}_{i=1}^{M}\). Thus, the beamforming vector \(\mathbf{w}\) is optimal unless all the coefficients \(\{\xi_{j}\}\) equal zero.  
Based on the SNR constrains, the optimal beamforming vector for the problem \(\mathcal{P}_{2}\) is given as \(\mathbf{w}^{\mathrm{opt}}=\sum_{i=1}^{M}\sqrt{\tau_{i}}\mathbf{h}_{i}/\| \mathbf{h}_{i}\|_{2}^{2}\) when the channels are orthogonal. The minimal transmit power is \(\|\mathbf{w}^{\mathrm{opt}}\|_{2}^{2}=\sum_{i=1}^{M}\tau_{i}/\|\mathbf{h}_{i} \|_{2}^{2}\). Since \(\|\mathbf{w}^{\mathrm{opt}}\|_{2}^{2}\approx\sum_{i=1}^{M}\tau_{i}/N\) as \(\mathbf{h}_{i}\sim\mathcal{CN}(0,\mathbf{I}_{N})\), the minimal transmit power is reduced by approximately \(\sum_{i=1}^{M}\tau_{i}/N(N+1)\) through adding one antenna. Therefore, when the channels are orthogonal, the decreasing speed of the minimal transmit power gets slower with the enlarge of the antenna size \(N\). Since the channels are asymptotically orthogonal but not exactly orthogonal, to satisfy all the constrains of the problem \(\mathcal{P}_{2}\), the beamforming vector \(\mathbf{w}\) should be scaled as \(\mathbf{w}=\zeta\mathbf{w}^{\mathrm{opt}}\) with \(\zeta=\max_{i}\sqrt{\tau_{i}}/\|\mathbf{h}_{i}{}^{H}\mathbf{w}^{\mathrm{opt}}\).  
The corresponding transmit power \(\|\mathbf{w}\|_{2}^{2}=\sum_{i=1}^{M}\tau_{i}\zeta^{2}/\|\mathbf{h}_{i}\|_{2} ^{2}\) will be an accurate approximation of the minimal transmit power when the channels are asymptotically orthogonal. To check the orthogonality of the channels, we investigate the correlation matrix \(C\) with \(C_{ij}=\frac{\|\mathbf{h}_{i}^{H}\mathbf{h}_{j}\|}{\|\mathbf{h}_{i}\|\|\mathbf{ h}_{j}\|}\). If \(C-\mathbf{I}_{M}\preceq\delta\), the channels are regarded as orthogonal and the minimal transmit power can be calculated more efficiently using the linear approximation instead of the SCA approach. Compared to the worst-case complexity \(\mathcal{O}(N^{3})\) per iteration for the SCA approach [5], the linear approximation introduced here merely has the complexity of \(\mathcal{O}(NK)\). Since the linear approximation has a much lower complexity, the MRDS algorithm is more efficient than the RDS algorithm. Apparently, the probability of channelorthogonality gets larger with the increase of the parameter \(\delta\), as a result, the MRDS algorithm turns to be more efficient. However, the linear approximation becomes inaccurate when \(\delta\) is large enough, so \(\delta\) should be determined as a compromise between the accuracy and the efficiency.