Spring 2014 ECE 6504 Probabilistic Graphical Models: Class Project

Virginia Tech

Multiple Input Multiple Output(MIMO) system are widely used in wireless technologies. MIMO systems have shown their capability to significantly improve both channel capacity and error rate performance. For an example, current deployed LTE system has 2 8 antennas at base station side, which can provide up to 300Mbps peak throughput (LTE). Very large MIMO system can offer very high spectral efficiencies.

The optimal way for MIMO detector is to use a maximum a posteriori (MAP) or maximum likelihood(ML)
detector. However the computational complexity increases exponentially with the number of antennas.
MAP detector has complexity as O(L^{N}). Spatial filtering(MMSE, ZF) has complexity as O(N^{3}). For
a MIMO system with 100+ antennas, the computational complexity with these methods are
prohibitive. So recently methods with probabilistic graphics model were studied as a competitive
solution for MIMO detector. We will discuss later, although running belief propagation on a fully
connected Markov Random Field (MRF) has same complexity as MMSE detector, there are
many proposals to reduce the complexity of BP detector, some detectors can have complexity as
O(N^{2})

For a MIMO system with N_{T} transmit and N_{R} receive antennas, can be modeled as

| (1) |

From transmitter side, information were modulated and mapped on to all N_{T} antennas. The narrowband
channel is represented by a matrix H of size N_{R} ×N_{T}, where each entry h_{i,j} defines a channel connecting
transmit antenna j and receive antenna i. The received signal, Y is the received vector of length N_{R}, and
noise N is a vector of Gaussian noise: N ~(0,σ_{n}^{2}I)

The optimal MAP detector enumerates all the elements of the joint posterior distribution

| (2) |

and then marginalizes out each variables:

| (3) |

Since we assume that the noise vectors, a jointly Gaussian complex random variables, are also i.i.d
and with with zero mean and same variance σ_{n}^{2}, then the pdf of noise vector can be shown
as

| (4) |

Assume that H is known for receiver by other means(Channel Estimation). Since n = y - Hx, we get

| (5) |

For most likelihood estimator, maximize equation 2 is not maximize equation 5. Maximize equation 5 is same to

| (6) |

Expand equation 6 and from the derivative, we can conclude that the optimal solution is

| (7) |

Here the MAP detector is same as MMSE detector since the model and mean of gaussian distribution are
same. MMSE detection has complexity of O(N^{3}), it becomes intractable even for configurations of
moderate size.

In order to reduce the complexity of decoder, approximate algorithms were proposed. We can expand equation 2 and equation 5 to get the P(x∣y,H). The joint distribution can be expressed as

| (8) |

where

| (9) |

| (10) |

| (11) |

| (12) |

The values of ϕ_{i}(x_{i}) and ψ_{i,j}(x_{i},x_{j}) given by equation 9 and equation 11 can be treated as node potentials
and edge potentials of an undirected graphical model to which we can apply belief propagation.

Belief propagation tries to estimate the marginal probabilities for all variables by means of passing messages between local nodes. The local belief at every node is calculated as the product of the local evidence and all incoming messages

| (13) |

where the message from node j to i, m_{ji}(x_{i}) represents the state in which x_{i} should be according to node
j.

From equation 7 we can also get similar presentation. As presented in [5], equation 7 can be rewritten as a linear problem form Ax = b,

| (14) |

where A = (H^{H}H) and b = H^{H}y. Linear problem can be solved with Gaussian Belief Propagation. The
idea is to convert Ax = b to an optimization problem

| (15) |

while define a PDF as p(x) = ^{-1}exp(-x^{T}Ax + b^{T}x). This is PDF is a multivariate gaussian distribution
with (A^{-1}b,A^{-1}). Since A = (H^{H}H) and b = H^{H}y, the PDF is now ((H^{H}H)^{-1}b,(H^{H}H)^{-1}).
This PDF can be rewritten similar with equation 8 while

| (16) |

| (17) |

Comparing equations from 8 to 12 with equation 16 17, we can see if we assume that P(x_{i}) is a constant,
which is true for scrambled encoder, two solutions are almost same with similiar node/edge potentials on a
pairwise MRF.

As deducted above, MIMO detector can use Gaussian belief propagation as a iterative solution. But
unfortunately, although the channel matrix H could be sparse, H^{H}H is a matrix with high density, so the
complexity is still high when the matrix size is big.

Gaussian Belief Propagation(GaBP) is a special case of continues belief propagation. Since the
underlying distribution is Gaussian, the algorithms can be simplified with simply rules, message
propagated are means and variance of distribution. There are some basic properties of gaussian
distribution which could be used to simplify message passing. As derived in [5], if there are two
gaussian random variables density functions (μ_{1},P_{1}^{-1}),(μ_{2},P_{2}^{-1}), the product of two
functions is also a gaussian distribution with (μ,P^{-1}), where μ = P^{-1}(P_{1}μ_{1} + P_{2}μ_{2}) and
P^{-1} = (P_{1} + P_{2})^{-1}

There is another interesting properties of gaussian belief propagation. Since gaussian distribution mode and mean are same, the max-product version of belief propagation and sum-product version of belief propagation are identical[5]. Since all messages are gaussian variables. Messages between different nodes can be simplified as message of mean and variance of a gaussian distribution.

| (18) |

Details of GaBP algorithms and matlab code can be found in [5].

Another interesting property of Gaussian belief propagation is the correctness of convergence. As studies of Turbo code and other topics demonstrated, Gaussian belief propagation converges to right means even with loopy topology. Weiss and Freeman [9] proved that with concept of ”unwrapped tree”, GaBP converges to right posterior means on any arbitrary topology, with single loop and with many loops.

In section 2.3, we conclude that GaBP can executed on a MRF represented by matrix H^{H}H. To get this
matrix, a matrix multiplication need to be performed, also the result matrix is a dense matrix, the
complexity is still too high.

D.Bickson proposed to construct an alternative matrix In[5].

| (19) |

where Ψ = σ^{2}I is the AWGN diagonal noise. And then define new vector of variables ≜{^{T},z^{T}}^{T},
where is the soution vector and z is an auxiliary vector. The new observation vector is ≜{0^{T},y^{T}}^{T}.
Then

| (20) |

This equation is similar with the graph proposed by Montanari in [2] for CDMA multi-user detection. The
graph model is exact what is shown in 1, a bipartite graph with N_{t} node at one side and N_{r}
nodes at other side. Although Montanari’s graph model is DAG, the graph model derived from
equation 19 and equation 20 is a UAG, which provides additional convergence and simpler update
rules.

The graphical model used in last section still a full connected graph with N_{t} × N_{r} edges. To reduce the
computational burden of message passing and marginalization, different solutions were studied. In[7]
Hu&Duman proposed to prune some edges for thick the corresponding variable and observation nodes are
weakly coupled together. The problem with this method is that we can not prune too many edges to ensure
reasonable performance.

An alternative strategy to prune edges is to prune edges via linear transformation. As mentioned in
introduction, sphere decoding is an algorithms widely used to decode MiMo. In sphere decoding, the QR
decomposition is first used to trianglularize the channel and then a tree search is applied for post joint
detection. In QR decomposition, the channel matrix H is decomposed into H = QR, here Q is square
matrix that Q^{H}Q = I and R is an upper triangular matrix. Then the original problem is projected to new
coordination y′ = Q^{H}y = Rx + Q^{H}n. If we run GaBP for this problem, the graphic model is shown in Fig
2. The total edges in GPM are 10 for a 4 × 4 MiMo system, 6 edges less than a full connected graph.

Another transformation studied [8] is bi-diagonalization of channel matrix, or it is called channel truncation, where the effective channel is given by

| (21) |

In [8], Viterbi algorithm was proposed to solve this formation, in PGM, it also has a straightforward model. With this channel matrix the GPM for a 4 × 4 MiMo channel can be shown as in Fig 3(a). Fig 3(b) is a re-arrangement Fig 3(a), which is basically a ring type of PGM. Total edges for a 4 × 4 MiMo system is 8. In[1], the ring type PGM MiMo detector was evaluated and the performance was reasonable after 4 6 iterations, with 0.3~1.0 dB difference.

Also as shown in [10], GaBP can be implemented with Gilbert Multiplier circuit directly. They demonstrated a MIMO detector with this analog circuit for the loopy structure shown in Fig 3(b), which provides a possibility to implement MIMO signal processing tasks with low-power analog circuity in continues time domain.

In the project, GPM based MiMo detector was studied, GPM built upon the original channel matrix was studied, further channel truncation and sphere MiMo detectors equivalent GPM model was introduced. With the proven algorithms as channel truncation and sphere detector, GPM version provides an iterative method with less computation burden. As suggested in other works, the GPM solution have more advantages for large MiMo system ISI channel, where the 3D channel matrix is big and sparse.

[1] Seokhyun Yoon, Jun Heo. Pair-wise Markov Random Fields Applied to the Design of Low Complexity MIMO detectors.

[2] Andrea Montanari, Balaji Prabhakar, David Tse. Belief Propagation Based Multi-User Dection.

[3] D.Bickson, O.Shental, PH.Siegel, J.K.Wolf, D.Dolev. Gaussian belief propagation based multiuser detection.

[4] J Soler-Garrido, R.J.Picchocki, K. Maharatna, D.McNamara. Analog MIMO detection on the basis of belief propagation

[5] Danny Bickson, Gaussian Belief Propagation:Theory and Application

[6] A Montanari, B Prabhakar, D Tse, Belief Propagation Based Multi-user detection

[7] Jun.Hu, T.M.Duman, Graph based detector for BLAST architecture

[8] Wen.Jiang,Ye,Li, XingXing Yu, 2007. Truncation for Low-Complexity MIMO signal detection.

[9] Y.Weiss ,W.T.Freeman, 1999, Correctness of belief propagation in Gaussian Graphical models of arbitrary Topology”

[10] J.S.Garrido, R.J.Picchocki, K.Maharatna 2006, Analog MIMO detection on the basis of belief propagation.