{'fraction_non_alphanumeric': 0.040363330125120306, 'fraction_numerical': 0.00697786333012512, 'mean_word_length': 4.588235294117647, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Gaussian Belief Propagation Based Multiuser Detection

In this work, we present a novel construction for solving the linear multiuser detection problem using the Gaussian Belief Propagation algorithm. Our algorithm yields an efficient, iterative and distributed implementation of the MMSE detector. We compare our algorithm's performance to a recent result and show an improved memory consumption, reduced computation steps and a reduction in the number of sent messages. We prove that recent work by Montanari et al. is an instance of our general algorithm, providing new convergence results for both algorithms.


I. INTRODUCTION
Belief propagation (BP), also known as the sum-product algorithm, is a powerful and efficient tool in solving, exactly or approximately, inference problems in probabilistic graphical models. The underlying essence of estimation theory is to detect a hidden input to a channel from its observed output. The channel can be represented as a certain graphical model, while the detection of the channel input is equivalent to performing inference in the corresponding graph.
The use of BP [1] for detection purposes has been proven to be very beneficial in several applications in communications. For randomly-spread code-division multiple-access (CDMA) in the large-system limit, Kabashima has introduced a tractable BP-based multiuser detection (MUD) scheme, which exhibits near-optimal error performance for binary-input additive white Gaussian noise (BI-AWGN) channels [2]. This messagepassing scheme has recently been extended to the case where the ambient noise level is unknown [3], [4]. As for sub-optimal detection, the nonlinear soft parallel interference cancellation (PIC) detector was reformulated by Tanaka and Okada as an approximate BP solution [5] to the MUD problem.
In contrast to the dense, fully-connected nature of the graphical model of the non-orthogonal CDMA channel, a onedimensional (1-D) intersymbol interference (ISI) channel can be interpreted as a cycle-free tree graph [6]. Thus, detection in 1-D ISI channels (termed equalization) can be performed in an optimal maximum a-posteriori (MAP) manner via BP, also known in this context as the forward/backward, or BCJR, algorithm [7]. Also, Kurkoski et al. [8], [9] have proposed an 1  iterative BP-like detection algorithm for 1-D ISI channels that uses a parallel message-passing schedule and achieves nearoptimal performance.
For the intermediate regime of non-dense graphs but with many relatively short loops, extensions of BP to twodimensional ISI channels have been considered by Marrow and Wolf [10], and recently Shental et al. [11]- [13] have demonstrated the near-optimality of a generalized version of BP for such channels. Recently, BP has been proved to asymptotically achieve optimal MAP detection for sparse linear systems with Gaussian noise [14], [15], for example, in CDMA with sparse spreading codes.
An important class of practical sub-optimal detectors is based on linear detection. This class includes, for instance, the conventional single-user matched filter (MF), decorrelator (a.k.a. zero-forcing equalizer), linear minimum meansquare error (MMSE) detector and many other detectors with widespread applicability [16], [17]. In general, linear detection can be viewed as the solution to a (deterministic) set of linear equations describing the original (probabilistic) estimation problem. Note that the mathematical operation behind linear detection extends to other tasks in communication, e.g. , channel precoding at the transmitter [18].
Recently, linear detection has been explicitly linked to BP [19], using a Gaussian belief propagation (GaBP) algorithm. This allows for a distributed implementation of the linear detector [20], circumventing the need of, potentially cumbersome, direct matrix inversion (via, e.g. , Gaussian elimination). The derived iterative framework was compared quantitatively with 'classical' iterative methods for solving systems of linear equations, such as those investigated in the context of linear implementation of CDMA demodulation [21]- [23]. GaBP is shown to yield faster convergence than these standard methods. Another important work is the BP-based MUD, recently derived and analyzed by Montanari et al. [24] for Gaussian input symbols.
There are several drawbacks to the linear detection technique of [19]. First, the input matrix R n×n = S T n×k S k×n (the chip correlation matrix) needs to be computed prior to running the algorithm. This computation requires n 2 k operations. In case where the matrix S is sparse [15], the matrix R might not no longer be sparse. Second, GaBP uses 2n 2 memory to store the messages. For a large n this could be prohibitive.
In this paper, we propose a new construction that addresses those two drawbacks. In our improved construction, given a non-rectangular CDMA matrix S n×k , we compute the MMSE detector x = (S T S + Ψ) −1 S T y where Ψ is the AWGN diagonal covariance matrix. We utilize the GaBP algorithm which is an efficient iterative distributed algorithm. The new construction uses only 2nk memory for storing the messages. When k ≪ n this represents significant saving relative to the 2n 2 in our previously proposed algorithm. Furthermore, we do not explicitly compute S T S, saving an extra n 2 k overhead.
We show that Montanari's algorithm [24] is an instance of our method. By showing this, we are able to prove new convergence results for Montanari's algorithm. Montanari proves that his method converges on normalized random-spreading CDMA sequences, assuming Gaussian signaling. Using binary signaling, he conjectures convergence to the large system limit. Here, we extend Montanari's result, to show that his algorithm converges also for non-random CDMA sequences when binary signaling is used, under weaker conditions. Another advantage of our work is that we allow different noise levels per bit transmitted.
The paper is organized as follows. Section II formulates the problem of linear detection and presents the distributed GaBPbased linear detection scheme. Section III describes a novel construction for efficiently computing the MMSE detector. The relation to a factor graph construction is explored in Section IV. New convergence results for Montanari's work are presented in Section V. We conclude in Section VI. In the Appendix we further explore the relation to Montanari's work.
We shall use the following notations. The operator {·} T stands for a vector or matrix transpose, the matrix I N is a N ×N identity matrix, while the symbols {·} i and {·} ij denote entries of a vector and matrix, respectively. N(i) is the set of graph node connected to node i.

II. LINEAR DETECTION VIA BELIEF PROPAGATION
Consider a discrete-time channel with a real input vector x = {x 1 , . . . , x K } T governed by an arbitrary prior distribution, P x , and a corresponding real output vector Here, the function f {·} denotes the channel transformation. By definition, linear detection compels the decision rule to bê where b = y is the K × 1 observation vector and the K × K matrix A is a positive-definite symmetric matrix approximating the channel transformation. The vector x * is the solution (over R) to Ax = b. Estimation is completed by adjusting the (inverse) matrix-vector product to the input alphabet, dictated by P x , accomplished by using a proper clipping function ∆{·} (e.g. , for binary signaling ∆{·} is the sign function). For example, linear channels, which appear extensively in many applications in communication and data storage systems, are characterized by the linear relation where n is a K × 1 additive noise vector and R = S T S is a positive-definite symmetric matrix, often known as the correlation matrix. The N ×K matrix S describes the physical channel medium while the vector y corresponds to the output of a bank of filters matched to the physical channel S.
Assuming linear channels with AWGN with variance σ 2 as the ambient noise, the general linear detection rule (1) can describe known linear detectors. For example [16], [17]: • The conventional matched filter (MF) detector is obtained by taking A I K and b = y. This detector is optimal, in the MAP-sense, for the case of zero cross-correlations, i.e. , R = I K , as happens for orthogonal CDMA or when there is no ISI effect. • The decorrelator (zero forcing equalizer) is achieved by substituting A R and b = y. It is optimal in the noiseless case. • The linear minimum mean-square error (MMSE) detector can also be described by using A = R + σ 2 I K . This detector is known to be optimal when the input distribution P x is Gaussian.
In general, linear detection is suboptimal because of its deterministic underlying mechanism (i.e. , solving a given set of linear equations), in contrast to other estimation schemes, such as MAP or maximum likelihood, that emerge from an optimization criterion.
In [19], linear detection, in its general form (1), was implemented using an efficient message-passing algorithm. The linear detection problem was shifted from an algebraic to a probabilistic domain. Instead of solving a deterministic vector-matrix linear equation, an inference problem is solved in a graphical model describing a certain Gaussian distribution function. Given the overall channel matrix R and the observation vector y, one knows how to write explicitly p(x) and the corresponding graph G with edge potentials ('compatibility functions') ψ ij and self-potentials ('evidence') φ i . These graph potentials are determined according to the following pairwise factorization of the Gaussian distribution p(x) The set of edges {i, j} corresponds to the set of all non-zero entries of A for which i > j. Hence, we would like to calculate the marginal densities, which must also be Gaussian, where µ i and P i are the marginal mean and inverse variance (a.k.a. precision), respectively. It is shown that the inferred mean µ is identical to the desired solution x * = R −1 y. Table I lists the GaBP algorithm update rules.  [25].

2.
Iterate Propagate P ki and µ ki , ∀k = i such that A ki = 0. Compute P i\j = P ii + k∈N(i)\j P ki and µ i\j = P −1 i\j (P ii µ ii + k∈N(i)\j P ki µ ki ).
Check If P ij and µ ij did not converge, return to #2. Else, continue to #4.

III. DISTRIBUTED ITERATIVE COMPUTATION OF THE MMSE DETECTOR
In this section, we efficiently extend the applicability of the proposed GaBP-based solver for systems with symmetric matrices [19] to systems with any square (i.e. , also nonsymmetric) or rectangular matrix. We first construct a new symmetric data matrixR based on an arbitrary (non-rectangular) matrix S ∈ R k×nR Additionally, we define a new vector of variablesx {x T , z T } T ∈ R (k+n)×1 , wherex ∈ R k×1 is the (to be shown) solution vector and z ∈ R n×1 is an auxiliary hidden vector, and a new observation vectorỹ {0 T , y T } T ∈ R (k+n)×1 . Now, we would like to show that solving the symmetric linear systemRx =ỹ and taking the first k entries of the corresponding solution vectorx is equivalent to solving the original (not necessarily symmetric) system Rx = y. Note that in the new construction the matrixR is sparse again, and has only 2nk off-diagonal nonzero elements. When running the GaBP algorithm we have only 2nk messages, instead of n 2 in the previous construction.
and extractingx we havê Note, that when the noise level is zero, Ψ = 0 m×m , we get the Moore-Penrose pseudoinverse solution

IV. RELATION TO FACTOR GRAPH
In this section we give an alternate proof of the correctness of our construction. Given the inverse covariance matrixR defined in (2), and the shift vectorx we can derive the matching self and edge potentials Next, we show the relation of our construction to a factor graph. We will use a factor graph with k nodes to the left (the bits transmitted) and n nodes to the right (the signal received), shown in Fig. 1. Using the definitionx {x T , z T } T ∈ R (k+n)×1 the vectorx represents the k input bits and the vector z represents the signal received. Now we can write the system probability as: It is known that the marginal distribution over z is: This distribution is Gaussian, with the following parameters: It is interesting to note that a similar construction was used by Frey [26] in his seminal 1999 work when discussing the factor analysis learning problem. While his work is beyond the scope of this paper, it can be shown that his algorithm can be modelled using the GaBP algorithm.

V. NEW CONVERGENCE RESULTS
One of the benefits of using our new construction is that we propose a new mechanism to provide future convergence results. In the Appendix we prove that Montanari's algorithm is an instance of our algorithm, thus our convergence results apply to Montanari's algorithm as well.
We know that if the matrixR is strictly diagonally dominant, then GaBP converges and the marginal means converge  to the true means [27,Claim 4]. Noting that the matrixR is symmetric, we can determine the applicability of this condition by examining its columns. Referring to (4) we see that in the first k columns, we have the k CDMA sequences. We assume random-spreading binary CDMA sequences which are normalized to one. In other words, the absolute sum of each column is √ n. In that case, the matrixR is not diagonally dominant (DD). We can add a regularization term of √ n + ǫ to force the matrixR to be DD, but we pay in changing the problem. In the next n columns of the matrixR, we have the diagonal covariance matrix Ψ with different noise levels per bit in the main diagonal, and zero elsewhere. The absolute sum of each column of S is k/ √ n, thus when the noise level of each bit satisfies Ψ i > k/ √ n, we have a convergence guarantee. Note, that the convergence condition is a sufficient condition. Based on Montanari's work, we also know that in the large system limit, the algorithm converges for binary signaling, even in the absence of noise.
An area of future work is to utilize this observation to identify CDMA schemes with matrices S that when fitted into the matrixR are either DD, or comply to the spectral radius convergence condition of [28].

VI. CONCLUSION
We presented a novel distributed algorithm for computing the MMSE detector for the CDMA multiuser detection problem. Our work utilizes the Gaussian Belief Propagation algorithm while improving two existing constructions [19], [24] in this field. Although we described our algorithm in the context of multiuser detection, it has wider applicability. For example, it provides an efficient iterative method for computing the Moore-Penrose pseudoinverse, and it can also be applied to the factor analysis learning problem [26].

OF OUR ALGORITHM
In this section we show that Montanari's algorithm is an instance of our algorithm. Our algorithm is more general. First, we allow different noise level for each received bit, unlike his work which uses a single fixed noise for the whole system. In practice, the bits are transmitted using different frequencies, thus suffering from different noise levels. Second, the update rules in his paper are fitted only to the randomlspreading CDMA codes, where the matrix A contains only values which are drawn uniformly from {−1, 1}. Assuming binary signalling, he conjectures convergence to the large system limit. Our new convergence proof holds for any CDMA matrices provided that the absolute sum of the chip sequences is one, under weaker conditions on the noise level. Third, we propose in [19] an efficient broadcast version for saving messages in a broadcast supporting network.
The probability distribution of the factor graph used by Montanari is: Extracting the self and edge potentials from the above probability distribution: For convenience, Table II provides a translation between the notations used in this paper (taken from [19]) and that used by Montanari et al. in [24]: Now we derive Montanari's update rules. We start with the precision message from left to right: Aji −js ib √ N .
By looking at Table 1, it is easy to verify that this precision update rule is equivalent to that in #2 of Table I. Using the same logic we get the precision message from right to left: The mean message from left to right is given by The same calculation is done for the mean from right to left: Finally, the left nodes calculated the precision and mean by The key difference between the two constructions is that Montanari uses a directed factor graph while we use an undirected graphical model. As a consequence, our construction provides additional convergence results and simpler update rules.