Filetype PDF | Posted on 03 Feb 2023 | 2 years ago
Authentication
digital resources
120x Filetype PDF File size 1.85 MB Source: lucris.lub.lu.se
Approximative Matrix Inverse Computations for Very-large MIMO and Applications to
Linear Pre-coding Systems
Prabhu, Hemanth; Rodrigues, Joachim; Edfors, Ove; Rusek, Fredrik
Published in:
[Host publication title missing]
2013
Link to publication
Citation for published version (APA):
Prabhu, H., Rodrigues, J., Edfors, O., & Rusek, F. (2013). Approximative Matrix Inverse Computations for Very-
large MIMO and Applications to Linear Pre-coding Systems. In [Host publication title missing] (pp. 2710-2715).
IEEE - Institute of Electrical and Electronics Engineers Inc..
Total number of authors:
4
General rights
Unless other specific re-use rights are stated the following general rights apply:
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors
and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the
legal requirements associated with these rights.
• Users may download and print one copy of any publication from the public portal for the purpose of private study
or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal
Read more about Creative commons licenses: https://creativecommons.org/licenses/
Take down policy
If you believe that this document breaches copyright please contact us providing details, and we will remove
access to the work immediately and investigate your claim.
Approximative Matrix Inverse Computations for
Very-large MIMO and Applications to Linear
Pre-coding Systems
Hemanth Prabhu, Joachim Rodrigues, Ove Edfors, and Fredrik Rusek
Department of Electrical and Information Technology, Lund University, Sweden
{Hemanth.Prabhu, Joachim.Rodrigues, Ove.Edfors, Fredrik.Rusek}@eit.lth.se
Abstract—In very-large multiple-input multiple-output slower rate than inner products of the propagation vectors
(MIMO) systems, the base station (BS) is equipped with very with themselves when the number of antennas grow, i.e.,
large number of antennas as compared to previously considered the user channels are asymptotically orthogonal. In [3], mea-
systems. There are various advantages of increasing the number surements in a realistic propagation environment for large
of antennas, and some schemes require handling large matrices
for joint processing (pre-coding) at the BS. The dirty paper array of antennas at a BS (up to 128 antennas at the BS
coding (DPC) is an optimal pre-coding scheme and has a and 26 different single antennas users) are performed. It
very high complexity. However, with increasing number of was shown that by using reasonably large antenna arrays it
BS antennas, linear pre-coding performance tends to that of is possible to decorrelate single user channels. Furthermore,
the optimal DPC. Although linear pre-coding is less complex in [4], residential area measurements for very-large MIMO
than DPC, there is a need to compute pseudo inverses of
large matrices. In this paper we present a low complexity system were performed, showing linear pre-coding sum rates
approximation of down-link Zero Forcing (ZF) linear pre-coding of up to 98% of those achieved by dirty paper coding (DPC),
for very-large multi-user MIMO systems. Approximation for BS to Mobile Station (MS) antenna ratios as low as 10.
using a Neumann series expansion is opted for inversion of
matrices over traditional exact computations, by making use
of special properties of the matrices, thereby reducing the cost Although there is a clear benefit of scaling up the number
of hardware. With this approximation of linear pre-coding, of BS antennas, including an almost (near) optimal linear pre-
we can significantly reduce the computational complexity for coding, the hardware cost and signal processing complexity
large enough systems, i.e., where we have enough BS antenna
elements. For the investigated case of 8 users, we obtain 90% can be very high. When using linear pre-coding, such as
of the full ZF sum rate, with lower computational complexity, Zero-Forcing (ZF), we can operate at the above mentioned
when the number of BS antennas per user is about 20 or more. BS/MS antenna ratios around 10 and the main source of
I. INTRODUCTION complexity for ZF pre-coding becomes the inverse of a K×K
Multiple-Input Multiple-Output (MIMO) techniques for matrix, where K is the number of users. The assumption of
wireless communication offer high data rates and reliabil- a significantly higher number of antenna elements does not
ity through the utilization of multiple transmit and receive affect the dimensions of this matrix, but it does offer the
antennas. These techniques are becoming more mature and opportunity to carry out the matrix inverse by much simpler
have been incorporated in advanced standards like LTE (Long means than outright inversion.
Term Evolution) Release 10 [1] to meet the International
Mobile Telecommunications-Advanced (IMT-A) requirements There are various hardware implementations for matrix
of gigabits-per-sec data rates. Basically, the more antennas the inversion using different algorithms, QR-Gram Schmidt [5],
transceivers are equipped with, the better performance can QR-Givens Rotation [6], and Gauss-Jordan [7]. While these
be obtained in terms of data rate, diversity (reliability) and methods are generic and work well for any type of matrix,
spectral efficiency. we can exploit the special structure of matrices appearing in
In [2], a Multi-User (MU) MIMO system with (an assump- very-large MIMO to reduce the complexity of the linear pre-
tion of) unlimited number of base station (BS) antennas in coding and make it more hardware efficient. To meet these
a multi-cell environment is investigated. It is shown that all objectives, approximations (using Neumann series) of matrix
the effects of uncorrelated noise and fast fading disappear, as inversion is opted rather than computing the exact inverse.
does the intra-cell interference. The assumption of an unlim- We describe the general setting in which our pre-coding is
ited number of BS antennas greatly simplifies the theoretical assumed to operate, discuss the linear class of pre-coders, and
analysis. However, it is obvious that in a practical system the finally focus on complexity of the ZF pre-coder, when using
numberofantennas cannot be arbitrarily large due to physical, QR-Gram Schmidt and Neumann series expansion to perform
cost, and power constraints. matrix inversion. We derive and compare complexity both in
The theoretical analysis in [2], assumes that inner products terms of the number of operations and the energy required to
between propagation vectors of different users grow at a perform the computations.
where P is a K × K diagonal matrix for power allocation.
Thesumrate is maximized by optimizing the power allocation
under the constraint that Tr(P) = 1, where Tr(·) is the trace
Pre-Coding operator.
Although optimal sum rate is achieved by DPC, this
(Base Station) approach is too resource expensive to be implemented in
Central Processing hardware and is used as a benchmark for ZF, Minimum Mean
Unit
Square Error (MMSE) and low complexity approximations of
ZF. The pre-coding matrix F can be decomposed as
1 √
F = √ W P; (4)
γ
Fig. 1: System model of a MU-MIMO system with M-antenna
base station and K single-antenna mobiles stations. where W represents a particular linear pre-coding algorithm,
and γ = ||Wp(P)||2 , is a power normalization factor, where
F
|| • ||F is Frobenius Norm.
II. SYSTEM DESCRIPTION A. ZF pre-coding scheme
The system model and the pre-coding in the following ZF linear pre-coding transmits user signals towards the
section is in line with the corresponding description in [8]. intended user with nulls steered in the direction of other users.
A MU-MIMO system model consists of a BS equipped with The ZF pre-coder is given as
Mantennas, which is simultaneously serving K single users
antenna, as shown in Fig.1. The received vector y of size W =H†; (5)
ZF
K×1is described as † H H −1
√ where H = H (HH ) is the pseudo-inverse of the
y = ρHz+n; (1) channel matrix H. A perfect CSI at the transmitter and nulling
makes this scheme interference free, and the sum rate is given
where H is the K ×M propagationmatrix of complex-valued as
K
channel coefficients, z is an M × 1 transmit vector, and n is X ρP
C = max log 1+ i : (6)
an additive noise vector with Independent and Identically Dis- ZF 2 γ
Tr(P)=1 i=1
tributed (IID) zero-mean and unit-variance complex Gaussian
random variables. The scalar ρ is a measure of the Signal-to- As the number of BS antennas M increases, H tends to
Noise Ratio (SNR) of the link, which is proportional to the have nearly orthogonal columns as the terminals are not
transmitted power divided by the noise-variance. Furthermore, correlated due to their physical separation. This assures that
it also absorbs various normalizing constants. The total trans- the performance of ZF pre-coding will be close to that of
mit power is normalized and independent of the number of optimal DPC pre-coding. However, ZF pre-coding requires
antennas M, the transmit vector z satisfies E{||z||2} = 1. computation of the pseudo-inverse (in (5)), which requires the
The pre-coding process at the transmit side is specified as computationally expensive inversion of a K ×K matrix.
z = Fx; (2) B. MMSE pre-coding scheme
MMSE pre-coding can trade interference reduction for
where F is a M ×K pre-coding matrix, x a K × 1 vector signal power inefficiency. The MMSE pre-coder is given as
containing user symbols, as described in [4].
Although the very-large MU-MIMO model is similar to a W =HH HHH+αI −1 ; (7)
MMSE
standard MIMO model, the increased number of BS antennas where α = K=ρ. At low SNRs (large α) the MMSE ap-
has several consequences. Things that were random before, H
proaches a Matched Filter (MF) pre-coder, i.e., W =H ,
now start to look deterministic. For example, the distribution MF
of the singular values of the channel matrix approaches a and at high SNRs (low α) it approaches the ZF pre-coder.
deterministic function [9]. Another observed property is that C. Low Complexity Pre-Coding
very wide (or tall) matrices tend to be very well conditioned.
A problem with both ZF and MMSE pre-coding is the
III. LINEAR PRE-CODING SCHEMES inverse operation of the K ×K matrix. Since the complexity
The optimal sum rate in the downlink of a MU-MIMO for both linear pre-coders is similar (when α is not large in
system with prefect channel state information (CSI) can be (7)), in this paper we analyse impact of low complexity (ap-
achieved by the interference pre-subtraction coding technique proximations) only on ZF pre-coder. A standard and expensive
called DPC [10]. The optimal sum rate is given as approach would be to compute the exact inverse of the matrix
Z(,HHH)in
C = max log det(I +ρHHPH);
DPC 2 (3) † H H −1 H −1
Tr(P)=1 W =H =H (HH ) =H (Z) : (8)
ZF
However, as the number of BS and MS antennas (M and The modification is described as follows. The scalar multi-
K) increases, the eigenvalues of the matrix Z converges to plication by δ=(M + K) in (12) is represented as a diagonal
a fixed deterministic distribution known as the Marchenko- matrix
Pastur distribution. Now following the analysis in [8], the D = δ I :
MP M+K K
largest and the smallest eigenvalues of Z converge to
Using this notation, (12) is rewritten as
1 2 1 2
λ (Z) −→ 1+√ ; λ (Z) −→ 1−√ ; L
max min
β β −1 X n
Z ≈ (I −D Z) D ; (13)
K MP MP
where (β = M=K), as M and K grows to infinity. By scaling n=0
the Z matrix with a factor β , the eigenvalues are found the accuracy of the approximation,for a given number of terms
1+β
in the region (L), depend on the size of the eigenvalues of (I − DMPZ).
√ Thesmaller their magnitude, the faster the convergence. Given
λ β Z −→ 1+2 β ; this, we want to pre-condition our matrix Z so that it will lead
max 1+β 1+β
to a fast convergence for a finite M and K system.
√ Now, assume that we want to pre-condition it with a diag-
λ β Z −→ 1−2 β : (9)
min 1+β 1+β onal matrix D, with non-zero diagonal entries. In principle,
Hence,theeigenvaluesofI −β=(1+β)Z = I −Z=(M+K) we would like to calculate the eigenvalues of (I − DZ) and
√ K √ K optimize D so that the magnitudes of the eigenvalues are as
lie in the range [−2 β=(1+β);2 β=(1+β)], where I is small as possible. This, however, is a complex and non-trivial
K
an K×K identity matrix. By asymptotically increasing β, the task. We will therefore use Gershgorins circle theorem [12] to
eigenvalues of I −Z=(M+K)lie in the range derive an upper bound of the magnitude of the eigenvalues.
K
" √ √ # By keeping this bound small, by selecting D, we can also
lim −2 β ; 2 β −→ [−0;0]: (10) guarantee that the magnitude of the eigenvalues are small.
β→+∞ 1+β 1+β In this derivation of the ”optimal” D we will assume that the
Hermitian matrix Z = HHH is diagonallydominant,meaning
Therefore, as β grows, the faster is the convergence of that the magnitude of the diagonal elements z are larger than
ii
1 n the sum of the magnitude of the off-diagonal elements in the
lim I − Z ≃0 : (11) P
n→∞ K M+K K same row, zij;i 6= j, namely that |zii| > |zij|. The
i6=j
It is known that if a matrix satisfies (11), its inverse can be largest magnitude of any eigenvalue of (I − DZ) is upper
bounded by
expressed by Neumann series [11] as
L X !
n
X max|λ | ≤ max |1−d z |+d |z | ; (14)
−1 δ δ i i ii i ij
Z ≈ I − Z ; (12) i i
M+K K M+K i6=j
n=0
and under the condition of a diagonally dominant Z, the
with equality when L grown to infinity, and δ < 1 is a smallest upper bound is obtained if d = 1=z . For this
attenuation factor introduced, since for finite M and K the i ii
selection of D we also have that max|λ | < 1, which
i
eigenvalues of channel realizations may lie outside the range i
specified in (9). For a feasible implementation of a matrix guarantees convergence of the Neumann series. Hence, our
inversion using Neumann series the number of iterations (L) final approximation of the inverse of a diagonally dominant
needs to be finite (or small). Z is a matrix D = diag(1=z11;1=z22;::::;1=zkk), the inverse
Theinverseof Z is approximatedby a summation of powers can be expressed using Neumann series as
of a matrix (or matrix multiplications) (12), which has a L
3 −1 X n
Z ≈ (I −DZ) D: (15)
complexity order O((L − 1) · K ). Although the complexity K
order can be equal or higher (depending on L) than computing n=0
the exact inverse (direct inversion, QR based etc), matrix Afast (or accelerated) way to compute the series (15) and
multiplications are preferable in hardware compared to exact (12), up to L = 2P −1 terms, where P is an integer, is to use
inversion. the identity
The convergence of (11) is based on the fact that the
L P−1
eigenvalues lie in the range given by (9) as M and K grows X n Y n
−1 2
Z ≈ (I −DZ) D= (I +(I −DZ) ) D;
asymptotically. However, for practical systems with finite M K
n=0 n=0
and K the eigenvalues may lie outside this range. In addition (16)
to what is described in [8], we introduce one modification of which leads to a numerical complexity proportional to the
the Neumann series inversion. It is based on the fact that the logarithm of the number or terms in the truncated series. In
closer the eigenvalues of our matrix are to 1, the faster the terms of number of matrix multiplications, the brute force
convergence of the series in (12). computation of the inverse using (15) (or (12)) would require
no reviews yet
Please Login to review.
