# Efficient Capacity-Based Joint Quantized Precoding and Transmit Antenna Selection Using Cross-Entropy Method for Multiuser MIMO Systems

Authors: Jung-Chieh Chen; Min-Han Chiu; Yi-Syun Yang; Kuan-Yuen Liao; Chih-Peng Li
Journal: International Journal of Antennas and Propagation
 (2012)

---

## Abstract

The current paper considers the joint precoding and transmit antenna selection to reduce
hardware cost, such as radio-frequency chains, associated with antennas in the downlink of multiuser
multiple-input multiple-output systems with limited feedback. The joint precoding and transmit
antenna selection algorithm requires an exhaustive search of all possible combinations and
permutations to find the optimum solution at the transmitter, thus resulting in extremely high computational
complexity. To reduce the computational load while still maximizing channel capacity,
the cross-entropy (CE) method is adopted to determine the suboptimum solution. Compared with
the conventional genetic algorithm and random search method, the CE method provides better
performance under the same computational complexity, as shown by the simulation results.


---

## Body

## 1.  Introduction

Studies have shown that the capacity of multiple-input multiple-output (MIMO) systems equipped with multiple antennas at both the transmitter and receiver sides increases almost linearly with the minimum number of transmit and receive antennas [1, 2]. Although systems employing a large number of transmit and receive antennas can improve their performance, two drawbacks are associated with such systems. First, the system requires the same number of radio-frequency (RF) chains as the antennas used, which typically increase the complexity and cost of system hardware. Second, in a multiuser scenario, a base station (BS) communicates simultaneously with several cochannel users in the same frequency and time slots, thereby degrading system performance [3].A promising solution to reduce the hardware complexity of RF chains is the concept of antenna selection scheme [4, 5], in which only the best subset of antennas is used, whereas the remaining antennas are not employed, thus reducing the number of required RF chains. Although antenna selection schemes have the potential to lower the hardware cost while retaining many diversity benefits of a MIMO system, they pose a new challenge to the optimal antenna selection, which requires an exhaustive search (ES) of all candidate combinations to achieve the best system performance. As a result, the computational load required for such optimal selection grows exponentially with the total number of antennas available. To reduce computational complexity, several suboptimal algorithms for antenna selection have recently been proposed, a summary of which can be found in [4, 5].To mitigate multiuser cochannel interference in a multiuser MIMO (MU-MIMO) scenario, transmit precoding is usually employed to achieve higher channel capacity [6]. However, transmit precoding generally requires accurate channel state information (CSI) at the transmitter, thus necessitating a huge amount of feedback from receivers. Unfortunately, the feedback rate is usually small in a practical MIMO system. Moreover, the precoding optimization problem is shown to be nondeterministic polynomial-time hard (NP-hard) [7–9]. To address these issues in a practical way, limited feedback is commonly used to convey the CSI to the transmitter. In addition, rather than directly sending the quantized version of the estimated CSI at the receiver back to the transmitter, a predetermined finite set of precoding vectors, referred to as the “codebook,” is selected based on predefined criteria and is fed back to the transmitter. As both the transmitter and the receiver know the codebook, only the index of the selected code word is delivered to the transmitter, reducing the feedback rate.To lower the hardware complexity and achieve superior performance in the MU-MIMO systems simultaneously, the overall system performance is greatly expected to benefit from the combination of the precoders and the transmit antenna subset selection [10–13]. However, in the conventional approaches, for example [10–12], the transmit antenna subset and the precoding vector selections are conducted separately, leading to performance loss. To fill the performance gap, Huang et al. [13] first formulated the problem of joint selection of the optimal Grassmannian precoders and transmit antenna subset in MU-MIMO systems, with limited feedback as a particular combination optimization problem. The genetic algorithm (GA) [14] is then applied to solve the problem. GA is a metaheuristic search method that is suitable for solving optimization problems. It encodes each candidate solution (called an individual) into a bit string (called a chromosome) and then associates it with an objective function. The general scheme for GA consists of five main procedures: initialization, evaluation, selection, crossover, and mutation. The first procedure, initialization, is used to randomly generate a genetic pool of NGA individuals to represent the NGA initial candidate solutions. The next procedure, evaluation, measures the fitness of each individual solution in the population and assigns to it a score. A proportion of the existing population with higher fitness is then selected to yield a new generation in the selection procedure. The selected individuals are crossed-over with the crossover probability in the crossover procedure. Finally, the mutation procedure is used to randomize the change of the selected individual solution with the mutation probability.Although the GA-assisted joint selection approach proposed in [13] outperforms the traditional separate scheme in terms of average capacity and bit error rate (BER) performance, the performance of the GA-assisted joint selection approach can be improved. Recently, Rubinstein proposed an innovative metaheuristic approach called cross-entropy (CE) method for global optimization [15]. The main idea of the CE method is to maintain a distribution of possible solutions and to update this distribution accordingly. Based on the importance sampling strategy, CE updates the distribution by minimizing the cross-entropy or Kullback-Leibler divergence to find the closest density to the optimal importance sampling one. In principle, GA and CE are population-based stochastic search methods. Unlike GA, however, CE uses the statistics of the entire population rather than the individual solutions to produce the next population, which increases the ability of CE to identify more global optima than GA. In addition, through the use of a smoothing parameter, CE avoids getting stuck at a local optimum. CE is also quite robust with respect to initial conditions and sampling errors, in contrast to other metaheuristics such as simulated annealing. Most importantly, CE is robust and efficient in practice, as well as possessing of asymptotic convergence properties. Based on the above points, the present paper proposes the application of the CE method to the problem described in [13]. Simulation results show that the proposed algorithm is superior to the GA method in terms of average capacity and BER performance under the same complexity.


## 2. System Model and Problem Definition

### 2.1. System Model

As shown in Figure1, a downlink MU-MIMO system with limited feedback is considered, in which the BS communicates with K active users over flat fading channels. Similar to [13], our MU-MIMO system is based on the following assumptions: (1) the BS is equipped with NT transmit antennas, whereas each user has NR receive antennas; (2) both the BS and the users know a codebook of 2L precoding vectors, where L is the number of feedback bits; (3) each user has perfect knowledge of its own CSI that can be used to select and find the index of the best precoding vector from the Grassmannian codebook [16].Figure 1
Transmitter structure of the considered hybrid scheme.Based on the above-mentioned assumptions, the signals received by thekth user can be described as (1)yk=HkFs+nk,
where yk∈ℂNR×1 is the received vector of the kth user, Hk∈ℂNR×NT is the channel matrix from the BS to the kth user, and s=[p1s1p2s2…pKsK]T is the transmitted vector from the BS, where (·)T denotes the transposition, and sk and pk are the binary phase-shift keying (BPSK) modulation symbol and the transmitted signal power for the kth user, respectively. Hence, the total transmit power can be expressed as ∑k=1K‍pk=p0. F=[f1f2…fK]∈ℂNT×K is the precoding matrix, where fk∈ℂNT×1 is the precoding vector for the kth user, which can be obtained based on the Grassmannian line-packing criterion [16], and nk∈ℂNR×1 is a Gaussian noise vector with zero mean and covariance matrix N0INR for the kth user, where INR denotes an NR×NR identity matrix.At the receiver side, a linear minimum mean square error (MMSE) MIMO detection is employed for each user to obtain better performance. After performing MMSE MIMO detection, the detected information signal for thekth user is given by (2)s^k=G~kyk.
Here, G~k is the linear MMSE decoding matrix of the kth user, which can be expressed as (3)G~k=hkH(H~kH~kH+KN0p0INR)-1,
where (·)-1 and (·)H denote the inverse of the matrix and the conjugation transpose operation, respectively; H~k=HkF is the equivalent channel matrix for the kth user after precoding, and hk=def[H~k]k=defHkfk, where [·]k denotes the kth column of the matrix.Given the above system model, the system capacity achieved by theK users can be expressed as (4)ℐcap(F,H1,…,HK)=∑k=1K‍log[1+SINRk(F,Hk)],
where SINRk is the output signal-to-noise plus interference ratio (SINR) obtained with the linear MMSE detection for the kth user, which is given by [17] (5)SINRk(F,Hk)=pk∥G~kHkfk∥2∑i=1i≠kK‍pi∥G~kHkfi∥2+∥G~k∥2N0.


### 2.2. Problem Statement

To reduce both the multiuser interference and hardware cost in the MU-MIMO downlink with limited feedback, a joint optimal precoding and transmit antenna selection scheme are proposed in [13] to maximize the system capacity as follows: (6)argmaxω∈Ωℐcap(Fωp,H1,ωt,…,HK,ωt),
where ωt is the selected subset of the antenna index for the transmitter, and vector ωt contains the elements of either 0 or 1 to indicate if a given antenna is selected. Hk,ωt is an NR×nT subblock matrix of Hk (i.e., the channel matrix associated with selected transmit antennas), in which nT≤NT is the desired number of transmit antennas to be selected; ωp is the selected subset of precoding vector index. ωp is the binary vector used to present the selected subset of the precoding vector index. Thus, the numbers of possible combinations for ωt and ωp are ℋ=CnTNT and ℱ=PK2L, respectively, where Cβα=α!/[β!(α-β)!] denotes the binomial coefficient and Pβα=α!/(α-β)! is the number of permutations of α distinct objects taken β at a time. For ease of presentation, we use ω=(ωp,ωt) to denote the joint precoding and antenna selection, thus obtaining 𝒜=ℱ×ℋ total number of all possible combinations. In addition, the set containing all the combinations of ω is defined as Ω={ω(1),…,ω(𝒜)}, where ω(q) denotes a particular combination, or ω∈Ω. Furthermore, we define ℐcap(ω)≡ℐcap(Fωp,H1,ωt,…,HK,ωt) for ease of notation.The choice ofω to maximize (6) is a combinatorial problem, and it can be achieved by ES. However, ES requires a large amount of computations to search all possible candidates, posing a potential problem for its practical implementation. To alleviate the computational load, suboptimal solution, such as the GA approach [13], may be used. However, the performance of GA still has room for improvement. Inspired by the success of the CE method in solving complex combinatorial optimization problems, we propose the application of the CE method to solve (6).


## 2.1. System Model

As shown in Figure1, a downlink MU-MIMO system with limited feedback is considered, in which the BS communicates with K active users over flat fading channels. Similar to [13], our MU-MIMO system is based on the following assumptions: (1) the BS is equipped with NT transmit antennas, whereas each user has NR receive antennas; (2) both the BS and the users know a codebook of 2L precoding vectors, where L is the number of feedback bits; (3) each user has perfect knowledge of its own CSI that can be used to select and find the index of the best precoding vector from the Grassmannian codebook [16].Figure 1
Transmitter structure of the considered hybrid scheme.Based on the above-mentioned assumptions, the signals received by thekth user can be described as (1)yk=HkFs+nk,
where yk∈ℂNR×1 is the received vector of the kth user, Hk∈ℂNR×NT is the channel matrix from the BS to the kth user, and s=[p1s1p2s2…pKsK]T is the transmitted vector from the BS, where (·)T denotes the transposition, and sk and pk are the binary phase-shift keying (BPSK) modulation symbol and the transmitted signal power for the kth user, respectively. Hence, the total transmit power can be expressed as ∑k=1K‍pk=p0. F=[f1f2…fK]∈ℂNT×K is the precoding matrix, where fk∈ℂNT×1 is the precoding vector for the kth user, which can be obtained based on the Grassmannian line-packing criterion [16], and nk∈ℂNR×1 is a Gaussian noise vector with zero mean and covariance matrix N0INR for the kth user, where INR denotes an NR×NR identity matrix.At the receiver side, a linear minimum mean square error (MMSE) MIMO detection is employed for each user to obtain better performance. After performing MMSE MIMO detection, the detected information signal for thekth user is given by (2)s^k=G~kyk.
Here, G~k is the linear MMSE decoding matrix of the kth user, which can be expressed as (3)G~k=hkH(H~kH~kH+KN0p0INR)-1,
where (·)-1 and (·)H denote the inverse of the matrix and the conjugation transpose operation, respectively; H~k=HkF is the equivalent channel matrix for the kth user after precoding, and hk=def[H~k]k=defHkfk, where [·]k denotes the kth column of the matrix.Given the above system model, the system capacity achieved by theK users can be expressed as (4)ℐcap(F,H1,…,HK)=∑k=1K‍log[1+SINRk(F,Hk)],
where SINRk is the output signal-to-noise plus interference ratio (SINR) obtained with the linear MMSE detection for the kth user, which is given by [17] (5)SINRk(F,Hk)=pk∥G~kHkfk∥2∑i=1i≠kK‍pi∥G~kHkfi∥2+∥G~k∥2N0.


## 2.2. Problem Statement

To reduce both the multiuser interference and hardware cost in the MU-MIMO downlink with limited feedback, a joint optimal precoding and transmit antenna selection scheme are proposed in [13] to maximize the system capacity as follows: (6)argmaxω∈Ωℐcap(Fωp,H1,ωt,…,HK,ωt),
where ωt is the selected subset of the antenna index for the transmitter, and vector ωt contains the elements of either 0 or 1 to indicate if a given antenna is selected. Hk,ωt is an NR×nT subblock matrix of Hk (i.e., the channel matrix associated with selected transmit antennas), in which nT≤NT is the desired number of transmit antennas to be selected; ωp is the selected subset of precoding vector index. ωp is the binary vector used to present the selected subset of the precoding vector index. Thus, the numbers of possible combinations for ωt and ωp are ℋ=CnTNT and ℱ=PK2L, respectively, where Cβα=α!/[β!(α-β)!] denotes the binomial coefficient and Pβα=α!/(α-β)! is the number of permutations of α distinct objects taken β at a time. For ease of presentation, we use ω=(ωp,ωt) to denote the joint precoding and antenna selection, thus obtaining 𝒜=ℱ×ℋ total number of all possible combinations. In addition, the set containing all the combinations of ω is defined as Ω={ω(1),…,ω(𝒜)}, where ω(q) denotes a particular combination, or ω∈Ω. Furthermore, we define ℐcap(ω)≡ℐcap(Fωp,H1,ωt,…,HK,ωt) for ease of notation.The choice ofω to maximize (6) is a combinatorial problem, and it can be achieved by ES. However, ES requires a large amount of computations to search all possible candidates, posing a potential problem for its practical implementation. To alleviate the computational load, suboptimal solution, such as the GA approach [13], may be used. However, the performance of GA still has room for improvement. Inspired by the success of the CE method in solving complex combinatorial optimization problems, we propose the application of the CE method to solve (6).


## 3. The Proposed CE-Based Approach

The CE method, proposed by Rubinstein and Kroese [15], is a type of important sampling technique for estimating the probabilities of rare events. Afterwards, it was modified to minimize the cross-entropy (also known as Kullback-Leibler distance) with respect to the optimal important sampling distribution and was evolved into the CE optimization [15]. The strength of the CE method lies in its ability to provide a systematic and efficient way to solve continuous and combinatorial optimization problems.In principle, the CE method is an iterative algorithm in which each iteration contains two main phases: first, a set of samples is generated according to a set of dynamic parameters; second, the set of dynamic parameters, which regulates the generation of random samples, is updated based on the selectedelite samples for producing better new samples. To apply the CE method in the joint precoding and transmit antenna selection problem, a family of probability densities {f(·,v)} has to be determined. This family has support 𝒜, and it is parameterized by v. Similar to the typical CE applications for discrete optimization problems, we can define a family of Bernoulli probability mass functions associated with the joint precoding and antenna selection vector ω={ωi}i=1NT+K×L, ωi∈{0,1}, as given by (7)f(ω,v)=∏i=1NT+K×L‍vi1i(ω)(1-vi)1-1i(ω),
where v={vi}i=1NT+K×L denotes the probability vector we need to update and the indicator function, 1i(ω)∈{0,1}, indicates whether the ith element of ω is selected. In short, ωi is generated according to the Ber(vi) distribution.In each iterationτ, NCE samples {ω(j,τ)}j=1NCE are drawn from the density f(·,v(τ-1)). From these samples, we calculate their fitness values {ℐcap(ω(j,τ))}j=1NCE using (4) and sort them in descending order such that ℐ~cap(1,τ)≥⋯≥ℐ~cap(NCE,τ), where ℐ~cap(j,τ) represents the jth order statistic of the sequence ℐcap(ω(1,τ)), ℐcap(ω(2,τ)), …,     andℐcap(ω(NCE,τ)). Then, the elite samples, which achieved the best performance in the current set, are collected according to the performance criterion, that is, the samples for which ℐcap(ω(j,τ))≥γ(τ) are selected. Here, γ(τ) is the threshold to determine the elite sample, which is set to (8)γ(τ)=ℐ~cap(⌈ρ×NCE⌉,τ),
where ρ∈(0,1) denotes the fraction of all samples, and ⌈·⌉ is the ceiling operation. Thus, these elite samples constitute an elite set Φ(τ), which is given by Φ(τ)={ω(j,τ):ℐcap(ω(j,τ))≥γ(τ)}.The goal of the CE method is to construct a sequence of parameter vectorsv(1),v(2),…,v(τ),…, such that ω(τ), approaching the global optimum ω⋆, can be obtained from f(·,v(τ)) as τ increases. Specifically, the CE method generates a sequence of couples (γ(τ),v(τ)) that steer the search towards a neighborhood of the optimal couple (γ⋆,v⋆). To achieve this goal, the CE method minimizes the cross-entropy between the updated random mechanism and the probability distribution of the selected elite samples as the update criterion. According to [15], the optimization problem of minimizing the cross-entropy to the optimal distribution f(·,v⋆) can be solved analytically, which is given by [15] (9)v(τ+1)=argmaxv{1NCE∑j=1NCE‍𝕀{j∈Φ(τ)}lnf(ω(j,τ),v)},where𝕀{j∈Φ(τ)} is an indicator variable defined by (10)𝕀{j∈Φ(τ)}={1,ifj∈Φ(τ)0,otherwise.The maximum of the CE program is determined by setting the first derivative of (9) with respect to v equal to zero, where (11)∂∂vilnf(ω(j,τ),v)=1i(ω(j,τ))-vivi(1-vi).
Thus,
(12)∂∂vi∑j=1NCE‍𝕀{j∈Φ(τ)}lnf(ω(j,τ),v)=1vi(1-vi)∑j=1NCE‍𝕀{j∈Φ(τ)}(1i(ω(j,τ))-vi)=0.
Solving for vi in (12) yields the estimate of the optimal probability density function (pdf) parameter. We have (13)vi=∑j=1NCE𝕀{j∈Φ(τ)}1i(ω(j,τ))∑j=1NCE𝕀{j∈Φ(τ)}
for i=1, …, NT+K×L.Remarks 1.
(
1
) The samples generated based on v(τ) cannot guarantee that the samples are feasible because the generated samples must satisfy the given constraints (i.e., the restricted number of the selected antennas). Therefore, we may need to add or remove randomly the necessary 1s for each generated sample to meet the constraint. (2) To prevent the CE method from premature convergence, a smoothing procedure is typically adopted to update the probability vector v as follows
(14)v(τ)=θ×v(τ)+(1-θ)×v(τ-1),whereθ∈(0,1] is the smoothing parameter. The updated v(τ) is then used in the next iteration for generating samples.(3) The parameters ρ and NCE determine how many “elite samples (=⌈ρ×NCE⌉)” should be chosen to produce better performing samples in the next iteration. In this case, the choice of ρ depends on the sample size NCE and the objective function of the considered problem. If sample size NCE is large, then ρ can be small. As a result, the obtained elite samples can provide enough data to produce better performing samples for the next iteration. On the other hand, if sample size NCE is not large enough, then ρ cannot be small. Otherwise, the proposed algorithm will be easily trapped in the local solutions. Generally, when we apply the CE for the considered problem, sample size NCE will be determined first. Afterwards, parameter ρ can be chosen. In practice, ρ is typically chosen from the range [0.01,0.1].The procedure for the proposed CE-assisted joint selection algorithm is summarized as follows.(1)
Set the iteration counterτ:=1 and initialize the probability vector v=[v1(0),…,vNT+K×L(0)] with vi(0)=1/2.(2)
DrawNCE random samples {ω(j,τ)}j=1NCE from the density function f(·;v(τ-1)).(3)
Randomly add or remove the necessary1s for each sample ω(j,τ) to ensure that each sample is ω(j,τ)∈Ω.(4)
Calculate their objective values{ℐcap(ω(j,τ))}j=1NCE.(5)
Use (8) to obtain γ(τ) to determine the elite set Ω(τ).(6)
Updatev(τ) using (13).(7)
Obtain the smoothedv(τ) using (14).(8)
Repeat Steps(2)–(7) for τ:=τ+1 until the predefined number of iterations is met.


## 4. Simulation Results

We compare the proposed CE method with the GA-based [13] and random search methods in terms of average system capacity, BER, and computational load. To determine the performance gap between the true optimal performance and the compared methods, we also adopt the ES algorithm as the reference bound. The simulation scenario is as follows [13]. A downlink MU-MIMO system with limited feedback is considered, with the data model described in (1). Here, we assume that i.i.d. BPSK modulated symbols are simultaneously sent from the transmit antennas of the BS to every user with equal energy through the i.i.d. Rayleigh fading channels. The number of users K, the number of transmit antennas at the BS NT, the number of selected transmit antennas nT, and the number of the receive antennas for each user NR are 2, 16, 4, and 2, respectively. In addition, the six-bit (L=6) Grassmannian codebook, which has 64 precoding vectors [16], is used for the precoding. In the parameters used in the proposed CE method, the smoothing parameter θ is 0.8 (The reasons for choosing θ=0.8 are based on the following: the recommendation of [15], which suggests the range for the design of 0.7<λ<1, and our simulation experience for this problem. We found empirically that a value of θ=0.8 gives good results.) and ρ is 0.1, and the algorithm is stopped when the iteration number exceeds the predetermined value.In the first simulation, we fix the signal-to-noise ratio (SNR) at 6 dB and determine how the capacity performances of the various algorithms are affected by the different number of searches𝒮. Here, the number of searches for GA and CE consists of the population size multiplied by the maximum number of iterations. The simulation results are shown in Figure 2, in which the population sizes for the CE and GA are NCE=NGA=840. The average capacity is evaluated over 10,000 independent trials. As expected, the average capacity increases when the number of iterations increases. It can be seen that the convergence speed of CE is low at the initial stage (i.e., when the total number of searches 𝒮 is small) because we do not have enough elite samples to produce better samples in the next iteration. Consequently, CE performs slightly worse than GA with a lower value of the total number of searches. After this initial stage, the proposed algorithm is superior to the GA and random search methods under the same number of searches. When the number of searches reaches approximately 16,800, the average capacity value is not improved further, and CE and GA converge to a reasonable solution. Therefore, the aforementioned three methods are realized with 𝒮=16,800 searches in the conducted simulations.Figure 2
Capacity versus the number of searches for different methods at SNR = 6 dB.Figures3 and 4 show the capacity and average BER performances, respectively, of the various algorithms with different SNRs. The following can be observed from the simulation results: (1) both the capacity and average BER performance improve as the SNR increases for all algorithms; (2) the proposed CE method always performs better than the GA and random search methods regardless of the SNR regions; and (3) both the capacity and average BER performance achieved by the optimum ES algorithm are always better than those obtained by the proposed CE method but at the cost of a much larger computational load, where the ES method requires 7,338,240 searches to obtain the optimum solution. A detailed complexity comparison between the CE method and the other algorithms is shown in Table 1.Table 1
Complexity of joint precoding and transmit antenna selection algorithms wherenT is the number of selected transmit antennas, NT is the number of total antennas, K donates the number of users, L donates the number of feedback bits, NGA and τGA are the population size and iterations used in the GA algorithm, and NCE and τCE are the population size and iterations used in the CE method.
Algorithms
Complexity order𝒪
(
N
T
,
n
T
,
K
,
L
)
=
(
16,4
,
2,6
)
Exhaustive search method
𝒪
(
C
n
T
N
T
×
P
K
2
L
)
7,338,240
GA method
𝒪
(
N
GA
×
τ
GA
)
16,800
CE method
𝒪
(
N
CE
×
τ
CE
)
16,800Figure 3
Capacity versus SNR for different methods.Figure 4
Average BER versus SNR for different methods.


## 5.  Conclusion

The current paper presents a CE-based scheme that realizes the joint precoding and transmit antenna selection in the downlink of MU-MIMO systems with limited feedback to reduce the interference effectively and lower the required RF chains. With the aid of the CE method, the large amount of search required can be successfully reduced. The simulations demonstrate that the proposed CE method not only provides better capacity performance but also enjoys complexity advantages compared with the conventional GA method.



---

*Source: 965834-2012-08-29.xml*