{'fraction_non_alphanumeric': 0.0514818938550448, 'fraction_numerical': 0.012088436456179418, 'mean_word_length': 4.1130387638926535, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Large-System Analysis of Joint User Selection and Vector Precoding with Zero-Forcing Transmit Beamforming for MIMO Broadcast Channels

Multiple-input multiple-output (MIMO) broadcast channels (BCs) (MIMO-BCs) with perfect channel state information (CSI) at the transmitter are considered. As joint user selection (US) and vector precoding (VP) (US-VP) with zero-forcing transmit beamforming (ZF-BF), US and continuous VP (CVP) (US-CVP) and data-dependent US (DD-US) are investigated. The replica method, developed in statistical physics, is used to analyze the energy penalties for the two US-VP schemes in the large-system limit, where the number of users, the number of selected users, and the number of transmit antennas tend to infinity with their ratios kept constant. Four observations are obtained in the large-system limit: First, the assumptions of replica symmetry (RS) and 1-step replica symmetry breaking (1RSB) for DD-US can provide acceptable approximations for low and moderate system loads, respectively. Secondly, DD-US outperforms CVP with random US in terms of the energy penalty for low-to-moderate system loads. Thirdly, the asymptotic energy penalty of DD-US is indistinguishable from that of US-CVP for low system loads. Finally, a greedy algorithm of DD-US proposed in authors' previous work can achieve nearly optimal performance for low-to-moderate system loads.


I. INTRODUCTION
Multiple-input multiple-output (MIMO) broadcast channels (BCs) (MIMO-BCs) are a model for the downlink of multiuser MIMO systems. The capacity region of the MIMO-BCs with perfect channel state information (CSI) at the transmitter has been shown to be achieved by dirty-paper coding (DPC) [1]- [4], which is a coding scheme to pre-cancel inter-user interference at the transmitter side [5]. Since DPC is infeasible in terms of complexity, it is an important research topic to construct a suboptimal scheme that can achieve an acceptable tradeoff between performance and complexity.
Zero-forcing transmit beamforming (ZF-BF) is a naive approach for eliminating inter-user interference at the transmitter [6], [7]. A drawback of ZF-BF is that the energy required for pre-cancellation of inter-user interference, called energy penalty in this paper, diverges as the system load increases. An increase of the energy penalty results in a degradation of the receive signal-to-noise ratio (SNR).
User selection (US) with ZF-BF [8], [9] is a promising approach when the number of users is much greater than the number of transmit antennas. Interestingly, it was proved that a greedy algorithm for US with ZF-BF can achieve the sum capacity of the MIMO-BC when only the number of users tends to infinity [9], [10]. This result is because it is possible to select a finite subset of users who have almost orthogonal channel vectors in that limit. As the number of transmit antennas increases, it becomes difficult to select such a subset of users, since the number of selected users should be increased to improve the throughput. This implies that US with ZF-BF is suboptimal in the situation where the number of transmit antennas is comparable to the number of users. Such a situation is becoming practical [11]. The goal of this paper is to construct a precoding scheme that works well in that situation.
Vector perturbation [12] or vector precoding (VP) [13] is a sophisticated precoding scheme suited for the situation where the number of transmit antennas is comparable to the number of users. In VP, the data vector is modified to take values in a relaxed alphabet [12], [13]. This relaxation reduces the energy penalty without degrading the minimum distance between the data symbols. As relaxed alphabets, a latticetype alphabet [12], [14] and a continuous alphabet [13] were proposed. In this paper, VP schemes with the lattice-type and continuous alphabets are referred to as "lattice VP (LVP)" and "continuous VP (CVP)," respectively. The search for a vector to minimize the energy penalty reduces to a convex optimization problem 1 for CVP, while the search problem for LVP is NP-hard. However, CVP might be still hard to implement since the convex optimization has to be solved every time slot. The goal of our research is to propose a more practical precoding scheme.
We propose joint US and VP (US-VP), and analyze the performance in the large-system limit, in which the number of transmit antennas N , the number of users K, and the number of selected usersK tend to infinity with the ratios α = K/N and κ =K/K kept constant. In this paper, ακ =K/N is referred to as the system load.
Data-dependent US (DD-US) proposed in [15] is regarded as a special case of US-VP, i.e. as US-VP with the original alphabet as the relaxed alphabet. DD-US takes into account the data symbols, along with the channel vectors, to reduce the energy penalty, as VP does. Furthermore, DD-US can be implemented with a suboptimal greedy algorithm [15]. The large-system analysis presented in this paper is based on the non-rigorous replica method, developed in statistical physics [16], [17]. The replica method is a powerful tool for analyzing the large-system performance of MIMO systems [13], [18], [19]. Several results based on the replica method have been justified rigorously. See [20]- [22] for the details.

II. MIMO BROADCAST CHANNEL
We consider a Gaussian MIMO-BC with perfect CSI at the transmitter, which consists of a base station with N transmit antennas and K receivers (users) with one receive antenna. The coherence time T c is assumed to be sufficiently long 2 . Let y k,t ∈ C denote the received signal for user k in time slot t (t = 0, 1, . . . , T c − 1). The received vector y t = (y 1,t , . . . , y K,t ) T in time slot t is given by In (1), u t = (u 1,t , . . . , u N,t ) T ∈ C N denotes a transmit vector in time slot t, defined in the next section. The (k, n)-element of the channel matrix H ∈ C K×N represents a complex channel gain between the nth transmit antenna and the kth user. The energy penalty E is defined as the time average of the power of the transmit vectors Thus, the prefactor E −1/2 in (1) implies that the transmit SNR is constrained to 1/N 0 . We assume that H is known to the transmitter, and that H has mutually independent circularly symmetric complex Gaussian entries with variance 1/N . These idealized assumptions allow us to calculate the energy penalty analytically. For simplicity, quadrature phase shift keying (QPSK) is used, and power allocation is not considered.

A. Zero-Forcing Transmit Beamforming
We start with the conventional ZF-BF [7], assuming K ≤ N . Let x t = (x 1,t , . . . , x K,t ) T denote the QPSK data symbol vector with unit power in time slot t. The transmit vector u t is linear-precoded as follows: Substituting (3) into (1) implies that inter-user interference is eliminated completely. More precisely, the MIMO-BC (1) is decomposed into single-user Gaussian channels with receive SNR 1/(EN 0 ). The drawback of ZF-BF is that the energy penalty (2) [23]. Consequently, the receive SNR tends to zero as α → 1. As a solution to circumventing the divergence of the energy penalty, VP has been considered.

B. Vector Precoding
In VP with ZF-BF, each data symbol x k,t is modified to take values in a relaxed alphabet X x k,t ⊂ C. The relaxed alphabets for different data symbols must be disjoint, i.e. X x ∩ Xx = ∅ for all x =x. Since information is conveyed by the relaxed alphabet X x k,t , the receiver detects the relaxed alphabet X x k,t . See [12] for the details. If one uses the vectorx t to minimize the energy penalty (2) as the modified vector, the transmit vector is given by Note that the vector (6) to minimize each instantaneous power u t 2 minimizes the energy penalty (2) for any T c .

Example 1 (LVP).
In LVP [12], two-dimensional (onecomplex-dimensional) square lattices are used as the relaxed alphabets, for It is infeasible in terms of the complexity to find the optimal vector (6) for LVP. Example 2 (CVP). In CVP [13], the original alphabets are relaxed to continuous disjoint alphabets, The minimization (6) for CVP reduces to a convex optimization problem, so that an efficient algorithm can be used to solve (6). However, CVP might be still hard to implement since the convex optimization needs to be solved every time slot.
The point of VP is that the modified vectorx t depends on the channel matrix H. Consequently, the energy penalty t for VP never tends to the righthand side (RHS) of (4) in T c → ∞. In fact, the energy penalty for VP was shown to be bounded in the limit α → 1 after taking the large-system limit [19].
C. Joint US and VP US-VP is performed every T time slots. The block length T should not be confused with the coherence time T c . We write the set of selected users in the ith block of US-VP as K i with |K i | =K, for i = 0, 1, . . .. The base station sends the QPSK data symbols {x k,iT +t : t = 0, . . . , T − 1} to the selected user k ∈ K i in block i. The transmit vector u t (t ∈ [iT, (i + 1)T − 1]) in block i is generated as where the set of selected users K i ⊂ K = {1, . . . , K} and the modified vectors {x Ki,t ∈ k∈Ki X x k,t } minimize the energy penalty (2): They are given by (11) at the top of this page. It is difficult to solve the minimization (11) for US-LVP and US-CVP, which are defined as US-VP with (7) and (8), respectively. Instead, we focus on DD-US.

Example 3 (Data-Dependent US). DD-US is defined as US-
VP with the original alphabet as the relaxed alphabet, i.e. X x = {x}. Since DD-US is performed every T time slots, DD-US may be more suitable for implementation. A greedy algorithm for DD-US with ZF-BF proposed in [15] allows us to solve the minimization (11) efficiently and approximately.
Let us discuss the relationship between DD-US and conventional US, the latter of which selects a subset of users K c ⊂ K to minimize the energy penalty Tr{(H Kc H H Kc ) −1 }. The energy penalty of the conventional US is obviously larger than that of DD-US for any T . In DD-US, the set of selected users K i is determined on the basis of an appropriate tradeoff (11) between the orthogonality of the channel row vectors and the direction of the data symbols. The performance of DD-US degrades as T increases, since it becomes difficult to select those data symbols with good direction. Thus, the energy penalty of DD-US in T → ∞ can be regarded as a lower bound on the energy penalty for the conventional US.
Each user has to detect whether he/she has been selected in each block of US. In order for each user to blind-detect it, the data symbols for non-selected users should be discarded at the transmitter side [15]. Substituting (10) into (1) yields for any k. In (12),x k,t ∈ X x k,t denotes the modified data symbol corresponding to the original data symbol x k,t . The variable s k,i ∈ {0, 1} indicating whether user k has been selected in block i is defined as Furthermore, h k ∈ C 1×N denotes the kth row vector of the channel matrix H. Note that the indices t of y k,t andx k,t in (12) are identical to each other, since the data symbols for the non-selected users k / ∈ K i have been discarded. This simplifies the detection of (13) [15].
It is easy for user k to blind-detect one variable s k,i from the T observations {y k,t } in each block. Using the decisionfeedback ofx k,t from the decoder improve the accuracy of detection [15]. In order to reduce the energy penalty, small T should be used. On the other hand, too small T makes it difficult to detect. As one option, dozens of time slots should be used as the block length T . For example, the energy loss due to detection errors is at most 0.2-0.5 dB for T = 16 [15].

IV. MAIN RESULTS
The replica method is used to analyze the energy penalty for US-VP in the large-system limit, where N , K, andK tend to infinity with the ratios α = K/N and κ =K/K kept constant. The energy penalty is expected to be self-averaging in the large-system limit: It converges in probability (or almost surely) to the expected one in the large-system limit. Thus, we focus on the average energy penalty.
We consider the assumptions of replica symmetry (RS) and of 1-step replica symmetry breaking (1RSB) [16], [17]. Roughly speaking, the RS assumption corresponds to the assumption that the solution to the minimization (11) is unique. On the other hand, 1RSB is the simplest assumption for the case in which there are many solutions. It is empirically known that the 1RSB assumption can provide a good approximation for the energy penalty [19].
Without loss of generality, we focus on the first block of US, i.e. t = 0, . . . , T − 1. Before presenting the main results, we summarize several definitions. Let us define a random variable E k (q) as with z k,t ∼ CN (0, 1). We write the cumulative distribution function Prob(E k (q) ≤ x) for the random variable (14) and its inverse function as F T (x; q) and F −1 T (x; q), respectively. We define two quantities µ κ,T (q) and σ 2 κ,T (q) as respectively. These quantities are associated with the mean and variance of where {E (k) (q)} are the order statistics of (14), i.e. E (1) (q) ≤ · · · ≤ E (K) (q) [24].

Proposition 1. Under the RS assumption, the average energy penalty per selected user E[E]/K for US-VP converges to
q 0 /(ακ) in the large-system limit, which is the solution to the fixed-point equation Proposition 2. Under the 1RSB assumption, the average energy penalty per selected user E[E]/K for US-VP converges to q 1 /(ακ) in the large-system limit, which satisfies the coupled fixed-point equations for some χ > 0, with See [25, Appendices C and D] for the details of the derivations. The central limit theorem implies that the random variable (14) converges in law to a Gaussian random in T → ∞. It is straightforward to find that (15) reduces to It is worth noting that the energy penalty of DD-US under the RS assumption is explicitly given by as the block length T tends to infinity. The energy penalty (23) under the RS assumption is equal to that for ZF-BF with random US (RUS), in whichK users are selected uniformly and randomly. Similarly, the energy penalty for US-CVP under the RS assumption is also equal to that for RUS and CVP (RUS-CVP) in T → ∞. Since the energy penalty for DD-US in T → ∞ is a lower bound on that for conventional US with ZF-BF, one may conclude that conventional US makes no sense in the large-system limit. However, we cannot reach this conclusion only from those observations. The RS solutions are approximations for the true energy penalty in the large-system limit. In order to investigate whether the conclusion is correct, the assumption of higher-step RSB should be considered.

V. NUMERICAL RESULTS
DD-US is compared to US-CVP, ZF-BF with RUS, and RUS-CVP [13] in terms of the average energy penalty. Note that the block length T is kept finite, while the coherence time T c is implicitly assumed to tend to infinity. We found that Propositions 1 and 2 for US-LVP provide unreliable approximations for the energy penalty, so that US-LVP is not plotted. The assumption of higher-step RSB is required to obtain a good approximation for US-LVP. Figure 1 shows the average energy penalties per selected user of the four schemes for T = 20 in the large-system limit. The RS and 1RSB solutions are plotted by dashed and solid lines, respectively. The energy penalties for a greedy algorithm of DD-US [15] are also shown for K = 128, 256, 512. The 1RSB assumptions are obviously unreliable for small ακ, since the energy penalties are larger than those for ZF-BF with RUS and RUS-CVP, which correspond to upper bounds. We can observe four results: First, the gap between the RS and 1RSB solutions for US-CVP is small for moderate-to-large ακ, while the gap for DS-US is for moderate ακ. Secondly, as the system size increases, the energy penalties for the greedy algorithm of DD-US [15] get closer from below to the RS solution for small ακ and to the 1RSB solution for moderate ακ, respectively. These results imply that the RS and 1RSB solutions for DD-US can provide acceptable approximations for small ακ and for moderate ακ, respectively. Thirdly, DD-US achieves almost the same energy penalty as US-CVP for low system loads. This result can be understood as follows: q in (14) is small for low system loads, so that the magnitude of is smaller than the magnitude of the data symbol with high probability. Thus, the continuous relaxation of the alphabet (8) makes no sense in this region of the system load. Finally, we find that DD-US outperforms RUS-CVP in terms of the energy penalty except for high ακ. For ακ = 0.5, DD-US can provide a performance gain of 1.8 dB, compared to RUS-CVP, which seems to be larger than the energy loss due to the detection error at the receiver [15], noted in the end of Section III-C. Note that the energy penalty for RUS-CVP gets closer from above to the asymptotic one as the system size increases [19]. Thus, the performance gap between DD-US and RUS-CVP should be larger for finite-sized systems.
We next assess the accuracy of the approximations based on the RS and 1RSB assumptions for DD-US. Figure 2 shows the average energy penalty per selected user versus α for fixed 0. ακ = 0.5. For comparison, the energy penalties for the greedy algorithm of DD-US [15] are also plotted. For small α, the RS and 1RSB solutions are indistinguishable from each other, so that they should provide an accurate approximation of the true energy penalty for small α. The gaps between the analytical results and the numerical simulations for small α should be due to the suboptimality of the greedy algorithm. The 1RSB solution for T = 80 exhibits strange behavior: The energy penalty must be a monotonically decreasing function of α, since large α implies large multiuser diversity. However, the energy penalty increases with the increase of α for large α.

VI. CONCLUSIONS
The energy penalties of DD-US and US-CVP for the MIMO-BC have been evaluated in the large-system limit under the RS and 1RSB assumptions. We found four observations: First, the RS and 1RSB assumptions for DD-US can provide acceptable approximations for low and moderate system loads, respectively. Secondly, DD-US outperforms RUS-CVP in terms of the energy penalty for low-to-moderate system loads. Thirdly, the asymptotic energy penalty of DD-US is indistinguishable from that of US-CVP for low system loads. Finally, a greedy algorithm of DD-US proposed in [15] can achieve nearly optimal performance for low-to-moderate system loads. These results imply that DD-US can provide a good tradeoff between the performance and the complexity for low-to-moderate system loads.
As another method for reducing the energy penalty, it is important to investigate regularized ZF-BF or minimum meansquared error (MMSE) precoding. We leave this analysis as future work.