{'fraction_non_alphanumeric': 0.041448308718437354, 'fraction_numerical': 0.00942247631147107, 'mean_word_length': 4.126729986431479, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tight Bounds on the Optimal UL Sum-Rate of MU RIS-aided Wireless Systems

The objective of this paper is to develop simple techniques to bound the optimal uplink sum-rate of multi-user RIS-aided wireless systems. Specifically, we develop a novel technique called \textit{channel separation} which provides a new understanding as to how the RIS phases affect the sum-rate. Leveraging channel separation, we derive upper and lower bounds on the optimal sum-rate. In addition, we propose a low-complexity alternating optimization algorithm to obtain near-optimal sum-rate results. Numerical results demonstrate the tightness of the bounds and show that the alternating optimization approach delivers sum-rate values similar to the results of a full numerical optimization procedure. Furthermore, in practical scenarios where hardware limitations cause the RIS phases to be quantized, our lower bound can still be applied and shows that the sum-rate is robust to quantization, even with low resolution.


I. INTRODUCTION
Reconfigurable Intelligent Surface (RIS) technology is designed to manipulate the channel between users (UEs) and base station (BS) via the RIS in a wireless system [1]. Assuming that channel state information (CSI) is known, then it is possible to intelligently configure the RIS phases to enhance performance metrics (e.g. energy efficiency [2]). However, it has become apparent that the unit modulus constraint introduced by the RIS phases leads to difficult, nonconvex optimization problems for most system metrics [3].
A very common optimization problem for wireless communication systems is to maximum the sum-rate among multiple users [3]- [6]. In [4] an iterative algorithm is proposed to maximize the sum-rate in the absence of a direct channel between the BS and users. Specifically, the DL sum-rate is maximized subject to discrete phases at the RIS and ZF beamforming at the BS given a maximum power threshold. The results presented show that good sum-rate performance can be achieved by a RIS of appropriate size along with low resolution for the RIS phases. Practically, it is difficult to implement continuous phase control for the RIS, so achieving near optimal performance with low phase resolution is important. The work in [5] is similar to that of [4] but considers a cell-free environment with multiple RIS deployed to aid transmission from a single BS. In [6] the sum-rate is maximized for an UL non-orthogonal multiple access (NOMA) system while successive interference cancellation (SIC) is performed at the single antenna BS in the absence of a UE-BS channel. To find the sub-optimal RIS phases, the authors reformulate the sum-rate maximization problem into the maximization of a quadratic form. The CVX package is then utilized to solve the related semi-definite-relaxation (SDR) problem. In multicell environments, [3] maximizes the weighted sum-rate of all users through a joint optimization of the precoding matrices at the BSs and of the RIS phases. The authors propose the use of Majorization-Minimization (MM) and Complex Circle Manifold (CCM) methods to optimize the RIS phases whilst keeping the precoding matrices fixed.
Due to the passive nature of the RIS, causing the unit modulus constraint, methods to compute sum-rate are usually algorithmic rather than closed form. Hence, in this paper, we make the following contributions: • We introduce a novel technique called channel separation which creates an equivalent channel matrix separated into two parts; one part is independent of the RIS and another part consists of a single row directly impacted by the RIS. Channel separation is designed for scenarios where the RIS-BS channel has a strong LOS component. • Leveraging channel separation, the problem of computing the optimal uplink (UL) sum-rate is reformulated to maximizing a simple quadratic form which leads to tight upper and lower bounds on the optimal sum-rate. • We propose a very low-complexity alternating optimization (AO) algorithm to obtain near optimum results. • Numerical results demonstrate the effectiveness of our techniques whilst showing that quantization of the RIS phases leads to little sum-rate degradation even with low resolution for the RIS phases. Notation: · 1 denotes the 1 norm. The transpose and Hermitian transpose are denoted as (·) T and (·) H respectively. The angle of a complex number, z, is denoted ∠z. The Kronecker product is denoted ⊗. U(a, b) denotes a uniform random variable taking on values between a and b, N (µ, σ 2 ) denotes a Normal distribution with mean µ and variance σ 2 and L(1/σ) denotes a Laplacian distribution with standard deviation parameter σ.

II. CHANNEL AND SYSTEM MODEL
As shown in Fig. 1, we examine a RIS-aided wireless system where a RIS with N reflective elements supports UL transmission between K single antenna UEs and a BS with M antennas.
Let H d ∈ C M ×K , H ru ∈ C N ×K , H br ∈ C M ×N be the UE-BS, UE-RIS, RIS-BS channels, respectively. The diagonal matrix Φ ∈ C N ×N , where Φ rr = e jφr for r = 1, 2, . . . , N , contains the reflection coefficients for each RIS element. Given these matrices, the global UL channel is given by, (1) In the channel model, we adopt a LOS version of the clustered, ray-based model in [7] for H d , H ru : with where C d , C ru are the number of clusters in the UE-BS, UE-RIS channels and S d , S ru are the number of sub-rays per cluster in the UE-BS and UE-RIS channels. In (2), κ d and κ ru are the equivalent of Ricean K-factors for the UE-BS and UE-RIS channels respectively, controlling the relative power of the scattered (ray-based) components and the LOS ray. For simplicity, we assume that each user has the same K-factor, but this can easily be generalized. B d , B ru are diagonal matrices containing the path gains between UE-BS and UE-RIS respectively, which are modeled by log-normal shadowing. In particular where d d,k and d ru,k are the distances between the k th UE and the BS and the k th UE and the RIS respectively, γ d and γ ru are the pathloss exponents, X d,k and X ru,k model the effects of shadow fading and are taken from a log-normal distribution with zero mean and variances σ 2 d,sf and σ 2 ru,sf respectively. P is the received power at a reference distance of 1m.
A LOS d and A LOS ru are the LOS components for the UE-BS and UE-RIS channels respectively. The k th columns of the LOS components for H d and H ru are given by where θ ru are the elevation angles of arrival (AOAs) for the k th UE and φ ru are the azimuth AOAs for the k th UE. Note that the steering vectors at the BS, a b (·, ·), and at the RIS, a r (·, ·), are topology dependent. Further details are given in Sec. V.
A SC d,s,c and A SC ru,s,c are the scattered components due to the s-th subray in the c-th cluster which are modeled as in [7]. The k th columns of A SC d,s,c and A SC ru,s,c are given by the weighted steering vectors, where θ ru,c,s are the elevation AOAs and φ ru,c,s . The majority of the results in this paper are for a pur LOS RIS-BS channel. However, we also show numerically that the results can be applied to scenarios where H br has a smaller scattered component and a dominant LOS path. Hence, we consider the following channel models: 1) H br is pure LOS: where θ br,A , φ br,A are the elevation and azimuth angles of arrival (AOAs) and θ br,D , φ br,D are the elevation and azimuth angles of departure (AODs), β br is the link gain between RIS and BS. Here, H br is rank-1 and the path gain is β br = d −2 br , where d br is the distance between RIS-BS.
2) H br is dominant LOS: such that η br >> ζ br , with where β br is the path gain between RIS-BS given by β br = d −2 br /η 2 br and A LOS br is given by (7). The A SC br,c,s matrices contain the scattered rays and are calculated in the same manner as for the other channels. κ br is the Ricean K-factor for the RIS-BS channel. In scenarios where the BS and RIS are located in close proximity, it is reasonable to assume that the RIS-BS channel is dominated by its LOS component [8].
Using (1) and the channels described above, the received signal at the BS is, where s is a K × 1 vector of transmitted symbols, each with a power of E |s k | 2 = E s and n ∼ CN (0, σ 2 I M ). For our results, we will assume that E s = 1 and σ 2 = 1.

III. CHANNEL SEPARATION
The optimal UL sum-rate, R opt sum , for the system in (9) is obtained by maximizing the traditional sum-rate expression for an UL MU-MIMO channel [9] over the possible RIS phases in Φ. Hence, we have Finding the optimal RIS phases to maximize the sum-rate is the associated design problem given by where the maximization is constrained over the unit amplitude diagonal entries in Φ.
(11) Note that a b and a r are used as simplified notation for the steering vectors in (7) for the H br channel. Since a H r ΦH ru is a row vector, we can confine the effects of Φ to one row of H by selecting U to satisfy The unitary matrix satisfying (12) Channel separation is observed in (13) where w H , the first row ofH, is the only row affected by Φ. Using (13), we can express the desired determinant as where (14) follows from the matrix determinant lemma.
In deriving (14), the SVD of the M × N matrix H br was used. However, the final solution can be written in terms of the channels only, making it computationally trivial involving only a K × K determinant and a K × K inverse. This is achieved by writing Using (14) and noting that Q is Hermitian, an equivalent statement of the maximization problem in (P.1) is argmax (P. 2) The benefit of channel separation is clearly seen in (P.2) where maximization is now over a simple scalar quadratic form. Furthermore, substituting u 1 = a b / √ M into Q and w gives so that all terms in the objective of (P.2) are simple functions of the channels.

IV. SUM-RATE MAXIMIZATION
In this section, we consider several low-complexity approaches to obtain sub-optimal solutions to the maximization problem (P.2) as well as lower and upper bounds to the optimal sum-rate. Expanding the quadratic form and using (16) we have  (14) and (17) this rank-1 component of the channel led to the scalar term x H Zx which dominates the effect of the RIS phases on sum-rate. Hence, we see that effective RIS phases must align strongly with Z.
Notice that if the constraint in (P.3) is relaxed to x H x = N , then the optimum solution, x , is proportional to the maximal eigenvector of Z. Direct computation of x requires the eigenvalue decomposition of a N × N matrix. Alternatively, a low complexity approach to computing x can be derived as The problem has been reduced from an N × N to a K × K eigenvalue decomposition, a considerable saving especially when considering large RIS sizes.

A. Lower bound on the optimal sum-rate
Due to (P.3) being non-convex, it is very difficult to obtain an exact optimal solution in closed form. As such, we will consider an alternative optimization problem, which is to obtain an approximate solutionx to (P.3). Specifically, we minimize the 1 -norm of the residuals between x in (18), the solution to the relaxed version of (P.3), and the approximate solution. Mathematically, the alternative optimization problem is min

B. Efficient alternating optimization algorithm
Here, we propose a low-complexity AO algorithm to find the RIS phases which maximize the sum-rate. The algorithm iteratively maximizes the n th RIS reflecting coefficient while keeping the other N − 1 coefficients fixed. We define the following vectors: where T 1 contains the terms not including e n , w 2n is the n-th element of w 2 and b n is the n-th column of B.
Since the quadratic form in (20) is positive, it is maximized over x n by maximizing 2 {x * n (b H n x (−n) + w 2n )}. Hence, in order to optimize the n th reflecting coefficient while the others coefficients are fixed, we can set x update n = e j∠(b H n x (−n) +w2n) .
(21) The computations involved in (21) are trivial as B and w 2 are one-off calculations requiring only a K ×K matrix inverse and matrix multiplications. Using (21) as the updating equation for each iteration in the algorithm, the AO algorithm is given in Algorithm 1.

Algorithm 1: Sum-Rate AO Algorithm
Result: RIS reflection coefficients, x Set algorithm precision threshold > 0 Set initial RIS coefficients to

C. Upper bound on the optimal sum-rate
Leveraging channel separation, we can also derive an upper bound on the sum-rate when the RIS-BS channel is LOS. Substituting (17) into (14), along with the Cauchy-Schwarz inequality to bound the elements of the second and third terms in (17), we have R sum ≤ log 2 (|Q|) where B = Z Q −1 Z H and p = Z Q −1 w 1 .

V. RESULTS
We now demonstrate the effectiveness of the different techniques presented in Sec. IV. Users were randomly located in a cell with a radius of 50m, outside an exclusion radius of 5m around the BS and RIS. As stated in Sec. II, the steering vectors used in the channels are topology dependent. We assume an M -element vertical uniform rectangular array in the y − z plane [7] with equal spacing in both dimensions at both the BS and RIS. The y and z components of a generic steering vector at the BS for a given elevation angle, θ, and azimuth angle, φ, are given by, . , e j2π(My−1)dr cos(θ) ] T , respectively where N = N y N z with N y , N z being the number of columns, rows of RIS elements, d r = 0.2 is the RIS element separation in wavelength units. The generic steering vectors at the BS and RIS are then given by, Note that (23) can be used to generate all of the channels in Sec. II by substituting the relevant elevation and azimuth angles. For the LOS components in channels H d and H ru , the elevation and azimuth AOAs for the k th UE are generated using θ ru ∼ U(−π/2, π/2). For the LOS component of H br , we assume that the elevation and azimuth angles are selected based on the following geometry representing a range of LOS links with less elevation variation than azimuth variation: For the rays in the scattered components, we model all central and deviation elevation angles by [7]: θ E,c,s ∼ L(1/σ E,s ) and the central and deviation azimuth angles by φ The subscript E ∈ {d, ru, br} represents the different channels. We assume that the parameter values for generating the subrays for each cluster are identical for both H d and H ru , and represent a broad spread of rays, as given in [7]. For channel H br , we assume that the rays are narrowly spread, for which the parameter values are also given in [7]. Specifically, the system parameter values are given in Table I   The path gain parameter, P , in (3) is selected such that the average total channel power for a single user is 0dB for a baseline case where M = 64, N = 100, κ d = κ ru = 0 and H br is pure LOS. This gives P = 45dB. The results for all simulations are averaged over 10 4 user locations and their associated path gains.
First, in Fig. 2, we demonstrate the effectiveness of the optimization techniques presented in Sec. IV for varying RIS sizes. Here, we show the lower bound (19), a 2-bit quantization of the lower bound, the AO algorithm shown in Alg. 1 and the upper bound given in (22). These expressions are computed for scenarios where κ ru = κ d = 1 and κ br = ∞ to represent a pure LOS RIS-BS channel The number of UEs is K ∈ {2, 5}. We compare these results against two benchmark cases: • the optimal sum-rate computed by built-in numerical optimization software using the interior point algorithm; • the sum-rate achieved by a random set of RIS phases selected from U(0, 2π). As can be seen in Fig. 2, the gain in sum-rate relative to random phases increases with N . The extremely simple upper and lower bounds derived via channel separation are shown to be very tight for all N . The simple AO approach gives results just below the interior point algorithm, possibly due to incomplete convergence or local maxima. However, the AO method remains efficient for large RIS sizes where runtime is a problem for the interior point algorithm. Note that quantizing the lower bound RIS design in (19) provides a lower bound on the sum-rate achievable by a quantized RIS, which is demonstrated in Fig. 2 for 2-bit RIS phases. As the lower bound in (19) and the AO approach are based an actual RIS designs assuming pure LOS for the H br channel, applying these solutions to any other channel also results in lower bounds, although they may be less tight. To study the robustness of the lower bound and the AO algorithm, we compare the sum-rate against a varying number of UEs for systems where κ d = κ ru = 1, κ br ∈ {∞, 1}, N ∈ {64, 144} and the results are shown in Fig. 3. As expected, since channel separation is designed for LOS RIS-BS channels, we see sub-optimal performance using the lower bound and the AO algorithm for increasing UEs and RIS sizes while the pure LOS channels give extremely accurate results. However, even with κ br = 1 (where the LOS and scattered powers are equal), the lower bounds are still reasonable. Hence, the simple bounds are still useful for RIS-BS channels which contain some scattering but have a dominant LOS component. In Fig. 4, we demonstrate the average efficiency of the AO algorithm by plotting the average sum-rates achieved at various iterations of the algorithm. Results are presented for systems with K = 2 and K = 4 UEs both with N ∈ {100, 121, 144}. The channel parameters are κ d = κ ru = 1 and κ ru = ∞. Even for large RIS sizes and increasing numbers of UEs,   3 shows that the algorithm converges very quickly. This is the property which enables rapid AO results to be obtained for large N , while numerical optimization becomes extremely slow.

VI. CONCLUSION
In this paper, we have presented a channel separation technique which allows for a new understanding on the effects of RIS phases on the sum-rate. Specifically, channel separation creates an equivalent channel matrix separated into two parts; one part is independent of the RIS and another part consists of a single row directly impacted by the RIS. Leveraging this technique, we derive extremely simple upper and lower bounds on the optimal sum-rate. In addition, we propose a low-complexity AO algorithm to obtain sub-optimal sum-rate results. Numerical results demonstrate the effectiveness of the presented techniques. Despite their simplicity, the bounds are shown to be very tight and the AO algorithm converges very quickly even for systems with large RIS sizes. In scenarios where hardware limitations are present, quantizing our proposed solutions leads to tight lower bounds on the sumrate achievable with quantized RIS designs and the resulting quantization degradation is shown to be minor. Although channel separation is designed for scenarios where the RIS-BS channel is LOS, the resulting lower bounds are demonstrated to be robust when the RIS-BS channel contains a weaker scattered component.