Figures
Abstract
We report a novel approach for inversion of large random matrices in massive Multiple-Input Multiple Output (MIMO) systems. It is based on the concept of inverse vectors in which an inverse vector is defined for each column of the principal matrix. Such an inverse vector has to satisfy two constraints. Firstly, it has to be in the null-space of all the remaining columns. We call it the null-space problem. Secondly, it has to form a projection of value equal to one in the direction of selected column. We term it as the normalization problem. The process essentially decomposes the inversion problem and distributes it over columns. Each column can be thought of as a node in the network or a particle in a swarm seeking its own solution, the inverse vector, which lightens the computational load on it. Another benefit of this approach is its applicability to all three cases pertaining to a linear system: the fully-determined, the over-determined, and the under-determined case. It eliminates the need of forming the generalized inverse for the last two cases by providing a new way to solve the least squares problem and the Moore and Penrose's pseudoinverse problem. The approach makes no assumption regarding the size, structure or sparsity of the matrix. This makes it fully applicable to much in vogue large random matrices arising in massive MIMO systems. Also, the null-space problem opens the door for a plethora of methods available in literature for null-space computation to enter the realm of matrix inversion. There is even a flexibility of finding an exact or approximate inverse depending on the null-space method employed. We employ the Householder's null-space method for exact solution and present a complete exposition of the new approach. A detailed comparison with well-established matrix inversion methods in literature is also given.
Citation: Anjum MAR, Ahmed MM (2014) A New Approach for Inversion of Large Random Matrices in Massive MIMO Systems. PLoS ONE 9(4): e94958. https://doi.org/10.1371/journal.pone.0094958
Editor: Shyamal D. Peddada, National Institute of Environmental and Health Sciences, United States of America
Received: November 26, 2013; Accepted: March 21, 2014; Published: April 14, 2014
Copyright: © 2014 Anjum, Ahmed. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Funding: The authors have no support or funding to report.
Competing interests: The authors have declared that no competing interests exist.
Introduction
Multiple-Input Multiple-Output (MIMO) systems form a well established area of wireless communications [1]. A significant increase in interest in MIMO systems has been witnessed in the last few years due to the advent of massive MIMO systems [2], [3]. In these systems, more degrees of freedom in terms of data rate and link reliability are available due to the increase in the number of transmit and receive antennas. These advantages become even more impressive in multi-user scenario when there is a possibility to transmit to several users simultaneously [2]. However, there is still a challenge of low complexity detection techniques for the practical realization of such systems [4]. Many high performance detection methods for massive MIMO systems require an unconstrained solution to a linear estimation problem [5]. Linear estimation requires the inversion of channel matrix which, in such systems, can be problematic because of its potentially large size. For example, matrices of size 40*40 and above have recently been reported in literature as massive [2].
Therefore, there is a need to find solutions that do not require outright inversion. Various methods in this regard have been proposed in literature: Cayley-Hamilton method, Neumann series method, QR method, random matrix methods, LSMR, LSQR, Kaczmarz method and the ones based on polynomial and truncated polynomial filters [6]–[19]. These methods still require a lot of computational effort and some of them have even proven to be more complex than the outright inversion [2], [6]. While it is possible that some may perform better than other, it is not always possible to have a fair comparison among them since these methods follow independent approaches and are dependent on different sets of parameters.
Keeping that in view, our objective in this paper is to develop an alternate method to find the inverse of the channel matrix. While addressing this problem, we dispense with three fundamental assumptions that are generally implied in the traditional methods. We endeavor to do so in order to provide more room for thought. First, no assumption has been made about the structure of the channel matrix. Secondly, the matrix can be purely random instead of being deterministic. Finally, we do not assume that it is sparse [20]. Keeping this in view, we report a novel method that not only finds the inverse of a channel matrix but also brings a new perspective to the inversion process itself. The proposed method is a comprehensive one and is fully applicable to all three matrix inversion cases pertaining to a linear system. We also provide its detailed comparison with well-known matrix inversion methods available in literature for the sake of analysis and, hence, understanding.
Rest of the article is organized as follows. To begin with, the subsequent section lays out basic system model and the essential nomenclature. The third section presents the basic idea behind the proposed method. The inversion problem is solved according to the proposed method using Householder's null-space method in the fourth section. In fifth section, solution to three fundamental cases of linear systems is presented. Proposed method is then compared with the QR decomposition (QRD) method, Least Squares (LS) method, and Moore and Penrose's pseudoinverse method in sections six, seven, and eight respectively. A complete algorithm for step by step computation of the inverse matrix according to the proposed method is outlined in section nine. Simulation results demonstrating the speed and accuracy of the proposed method in comparison to the state of the art methods available in literature are presented in section ten. Finally, the article concludes with a brief discussion in section eleven.
System Model
A MIMO system is represented by a system of linear equations [21].(1)
is the channel matrix of dimension
,
is the transmitted vector of dimension
, and
is the received vector of dimension
. Entries of
matrix are complex-valued independent and identically distributed Gaussian random variables of zero mean and unity variance [6].
and
are the number of transmit and receive antennas respectively. If
, the number of equations is equal to the number of unknowns and the system is fully-determined. If
, the number of equations is greater than the number of unknowns and the system is over-determined. If
, the number of equations is less than the number of unknowns and the system is under-determined.
Basic Idea
We begin with the assumption that has a full-rank. Re-writing Eq. (1) as:
(2)
First term on the right hand side of Eq. (2) denotes -th column of matrix
.
is the associated unknown. The second term represents the remaining columns of
with their respective unknowns. This term can be separately written in matrix form by defining a new column reduced matrix
and a symbol reduced vector
.
(3)
has dimensions of
. Taking the dot product of Eq. (3) with an arbitrary column vector
of dimension
,
(4)
To evaluate the j-th unknown from Eq. (4),
(5)
(6)
Eqs. (5) and (6) define the -th row of the inverse matrix. It should have a dot product of one with the
-th column and zero with all the remaining columns. The same is also true for all the other rows of the inverse matrix. Once we are able to solve Eqs. (5) and (6) for
, all rows of inverse matrix can be computed one by one in the same fashion and a complete inverse matrix can be built. Eq. (5) essentially restricts the length of the null-space solution produced by Eq. (6) and serves as a constraint for Eq. (6). Therefore, we proceed by solving the Eq. (6) first. It can be solved by a variety of methods available in literature of for computing the null-space of a matrix. We propose to solve it by Householder's null-space method because it is stable and provides an exact solution.
Solution Using Householder's Null-Space Method
Householder's method has been traditionally viewed as a means to achieve the QR decomposition (QRD). It performs a series of orthogonal transformations on an arbitrary matrix to convert it to an upper triangular matrix. These transformations can be performed either by Given's rotation matrices or Householder's reflection matrices. A reflection matrix can perform the job of many rotation matrices at once. Therefore, reflection matrices are more desirable in our case. We proceed by performing a series of orthogonal transformations on the matrix using the reflection matrices to convert it to an upper triangular matrix
.
reflection matrices will be required for that purpose because
has
columns.
(7)
's represent the Householder's reflection matrices. They are square, symmetric and orthogonal with each one having the dimensions of
.
has also the same dimensions. But the dimensions of
are
. This is because the first
rows of
generate an
upper triangular portion in
. Remaining
rows in
are zero. These rows are produced by last
rows of
.
(8)
(9)
's mark the rows that produce zeros in
matrix. Substituting Eqs. (8) and (9) in Eq. (7),
(10)
Concentrating on 's only in Eq. (10),
(11)
's form the basis for the left null-space of
and, hence, solve Eq (6). Only equation that remains to be solved now is Eq. (5). In order to do so, we would need to consider the three fundamental cases of linear systems.
Three Fundamental Cases
In this section, we take up the three fundamental cases of linear systems and solve them one by one.
1. The Fully-Determined Case
In the fully-determined case, there is only one vector in the left null-space of , i.e.,
given that
. The solution in Eq. (11) is unique.
(12)
The only remaining task is to rescale according to Eq. (5).
(13)
is the rescaling factor for the j-th row of inverse matrix
. By iterating
for all columns of
matrix, complete inverse matrix
can be built.
(15)such that,
The identity matrix will have the dimensions of .
2. The Over-Determined Case
In the over-determined case, the matrix will already have a right null-space due to a greater number of rows than the columns. The removal of extra column to form
will populate the null-space even further and there will be
vectors in the left null-space of
. Hence, the solution to the Eq. (6) will not be unique.
(16)
All the vectors from to
solve Eq. (6). An obvious question would be which one to choose. At this point, we adjourn this question to Section VIII where it would be amply addressed. For now, any one of them can be selected. The next step would be to rescale it according to Eq. (13). By repeating the same procedure for all columns of
, a complete inverse matrix can be built.
3. The Under-Determined Case
In the under-determined case, matrix will have right null-space due to a greater number of columns than the rows. In order to be consistent with the earlier work, we can transpose it and move the null-space to left. The inverse matrix can then be computed in the manner described in subsection (b). Only a transposition of inverse matrix is required afterwards to revert to the original case.
Comparison with QR Decomposition
Traditional methods employing QR decomposition take a linear system of the form,(17)into,
(18)
by factorizing in Eq. (17) into an orthogonal matrix
and an upper-triangular matrix
[22]. There are two famous ways for achieving QR decomposition: Gram-Schmidt QR and Householder's QR [22]. Traditionally, Gram-Schmidt method has been used for that purpose. Objective was to convert an
matrix
into an
orthogonal matrix
. Matrix
connects
to
.
(19)
Householder's method takes a shift in perspective. is targeted instead of
. Being an upper triangular matrix,
is much more suitable for back substitution.
serves as the connecting matrix.
(20)
The in Eq. (20) has extra
columns than the one obtained by Gram-Schmidt method. First
columns serve as the orthonormal basis for the column space of
. Remaining
columns form the basis for the left null-space of
because
can only be made triangular upto first
rows. [22].
(21)
In the proposed method, Househoder's method is employed to find the null space basis of
. Also, there is a difference in the orientation of
in Eq. (8) which leads to,
(22)
instead of . We take
as such because its last
rows are responsible for the zero last
rows of
. Orthonormal column space of
in Eq. (20) is now an orthonormal row space in Eq. (22).
Comparison with Least Squares
When has fewer columns than the rows, the system becomes over-determined. There are more equations than the unknowns. The solution is then obtained by Least Squares (LS).
(23)
QR decomposition is a popular method to solve LS problems and when applied to Eq. (23) will result in Eq. (18).
We have not approached the over-determined case using LS. We have taken it column by column. A dearth of columns in an over-determined matrix signals an apriori presence of the left null-space. Removal of one more column will populate it further. This will bring us to select, out of this abundance of null-space vectors, the one which has the highest value of depicted in Eq. (14). It needs to be so because the selected vector will then be divided by
according to Eq. (13). Smaller values of
can inflate the magnitude of the null-space vector after division. In the worst case of
, there will be a division by zero. Therefore, out of many null-space vectors obtained by Householder's null-space method, the best would be the one which has the highest value of
for the specific column vector. The term best can be pushed even further. In ideal case, a value of one for
would imply no division at all. But the caveat is to avoid smaller values of
in order to prevent instability.
Comparison with Moore and Penrose's Pseudoinverse
Now we turn to the last case, the case when the matrix is singular. A solution in this case is sought by forming the Moore and Penrose's pseudoinverse. Not an exact inverse though, the idea is to find the shortest vector that solves the LS equation. The term shortest implies a vector that has no null-space component. One way to do is to use Singular Value Decomposition (SVD) [20]. SVD decomposes the matrix
into two square, orthonormal matrices
and
. These matrices contain the basis for the column and row space of
respectively.
(24)
The third matrix is a diagonal matrix that contains the singular values. Some of the singular values in
will be zero for this case due to the presence of dependent columns in
. Columns of
and
for the corresponding zero singular values will represent the left and right null-spaces of
. Pseudoinverse is formed by leaving the zero singular values unchanged while inverting the others. This gives the shortest solution in row space.
At this point, a matrix with all entries equal to one would serve best to explain our approach. Once the first column is removed, Eq. (6) will seek a solution in the left null-space of the remaining columns. Eq. (5) will dictate this solution to have a projection of value equal to one with the removed column. This is impossible because both the removed column and the remaining column are exactly the same. A vector cannot be orthogonal and parallel to itself at the same time. In our opinion, this is precisely the reason for non-invertibility of a matrix rather than the traditional zero-determinant view. The only unique vector is the vector left in the column space of
, the only remaining column. Therefore, it is rescaled with itself to satisfy Eq. (13). This is exactly the solution obtained by applying the SVD to above problem.
Algorithm
We summarize the steps discussed in the form of a complete algorithm as follows.
- If
, continue to step 2, otherwise transpose the matrix
before moving to step 2.
- Locate the j-th column whose inverse vector is to be determined.
- Remove that column from
matrix to form a new matrix
.
- Decompose
to form
and
matrices according to Eq. (7).
- Discard the
matrix and the first
rows of
matrix.
- Remaining
rows will constitute null-space of
. In case
, there will be only one row and, hence, one candidate for the inverse channel vector. In case
, all of the remaining
rows satisfy the criteria in Eq. (6). In this case, pick any one at random.
- Normalize the selected vector according to Eqs. (13) and (14) to form the inverse vector
.
- Go back to step 2 and repeat the same procedure for the remaining columns of
matrix.
- Stack the inverse channel vectors on top of each other in the manner described in Eq. (15) to form the complete inverse matrix
.
- For the case when
, transposition of
formed in step 9 is necessary to form the right handed inverse.
A user-friendly code of this algorithm is provided in Code S1.
Simulation Results
We now present the simulation results of the algorithm. The components of the channel matrix are chosen to be independent and identically distributed (IID) circularly symmetric Gaussian random variables with a zero mean and unity variance. is selected to be equal to
as this refers to multi-user case in M-MIMO systems because both the number of transmitting and receiving antennas become very large. For example, a typical matrix size can be
and above [2]. Also when
, an exact solution is possible and the residue and hence the error in the estimate can be zero.
For simulation purpose, various matrix sizes have been selected and the results obtained in terms of the norm of residue, norm of the error in estimate and the computational time taken are displayed in Table 1 against the state of the art algorithms available in literature: LSMR, LSQR, and Kaczmarz method. Since the proposed method achieves zero error/residue norms, its respective columns are not displayed in the table. Codes required for simulation of LSQR and LSMR algorithms have been downloaded from the website of Stanford University's System Optimization Laboratory and are used as is.
Simulation results demonstrate that when LSMR, LSQR, and Kaczmarz method are applied to this problem, these methods suffer from very large residue norms. But that is not all. The norms for the error in estimate are even worse. Kaczmarz method is not only the slowest of all but also has largest error/residue norms. Hence, the estimates become practically useless. On the other hand, the proposed method achieves perfectly zero error/residue norms in moderate time. Therefore, the proposed method can be a much better choice in this context due to its better accuracy and speed.
Conclusion
A novel approach for matrix inversion has been presented in this paper. The matrix was split into a set of column reduced matrices, each with its own inverse channel vector . In order to qualify for an inverse channel vector,
had to satisfy two constraints;
and
. Householder's null-space method was used to solve the first constraint and scaling was used to solve the second one. Inverse matrix was then built from these inverse channel vectors. A detailed comparison with the state of the art methods available in literature was carried out all along to emphasize the novelty of the method.
Supporting Information
Code S1.
A user-friendly code of the proposed algorithm.
https://doi.org/10.1371/journal.pone.0094958.s001
(ZIP)
Author Contributions
Conceived and designed the experiments: MARA. Performed the experiments: MARA. Analyzed the data: MARA. Contributed reagents/materials/analysis tools: MARA. Wrote the paper: MARA. Played the role of supervisor in this research: MMA.
References
- 1. Paulraj AJ, Gore DA, Nabar RU, Bolcskei H (2004) An overview of MIMO communications - a key to gigabit wireless. Proceedings of the IEEE 92: 198–218.
- 2. Rusek F, Persson D, Buon Kiong L, Larsson EG, Marzetta TL, et al. (2013) Scaling Up MIMO: Opportunities and Challenges with Very Large Arrays. IEEE Signal Processing Magazine 30: 40–60.
- 3. Vishnu Vardhan K, Mohammed SK, Chockalingam A, Sundar Rajan B (2008) A low-complexity detector for large MIMO systems and multicarrier CDMA systems. IEEE Journal on Selected Areas in Communications 26: 473–485.
- 4. Yi W, Leib H (2013) Sphere Decoding for MIMO Systems with Newton Iterative Matrix Inversion. IEEE Communications Letters 17: 389–392.
- 5. Hochwald BM, Ten Brink S (2003) Achieving near-capacity on a multiple-antenna channel. IEEE Transactions on Communications 51: 389–399.
- 6.
Couillet R and Debbah M (2011) Random Matrix Methods for Wireless Communications. Cambridge University Press. 568 p.
- 7.
Edman F and Owall V (2003) Implementation of a scalable matrix inversion architecture for triangular matrices. 14th IEEE 2003 International Symposium on Personal, Indoor and Mobile Radio Communications Proceedings, 7-10 Sept 2003. Piscataway, NJ, USA: IEEE. pp. 2558–2562.
- 8.
Golub GH and Loan CFV (1996) Matrix computations (3rd ed.). Johns Hopkins University Press. 694 p.
- 9. Honig ML, Weimin X (2001) Performance of reduced-rank linear interference suppression. IEEE Transactions on Information Theory 47: 1928–1946.
- 10.
Karkooti M, Cavallaro JR and Dick C (2005) FPGA implementation of matrix inversion using QRD-RLS algorithm. 2005 39th Asilomar Conference on Signals, Systems and Computer, 30 Oct-2 Nov 2005. Piscataway, NJ, USA: IEEE. pp. 1625–1629.
- 11. Lei M, Dickson K, McAllister J, McCanny J (2011) QR Decomposition-Based Matrix Inversion for High Performance Embedded MIMO Receivers. IEEE Transactions on Signal Processing 59: 1858–1867.
- 12. Muller RR, Verdu S (2001) Design and analysis of low-complexity interference mitigation on vector channels. IEEE Journal on Selected Areas in Communications 19: 1429–1441.
- 13.
Stewart GW (2001) Matrix algorithms. Society for Industrial and Applied Mathematics. 469 p.
- 14.
Wu D, Eilert J, Liu D, Wang D, Al-Dhahir N, et al. (2007) Fast complex valued matrix inversion for multi-user STBC-MIMO decoding. IEEE Computer Society Annual Symposium on VLSI: Emerging VLSI Technologies and Architectures, ISVLSI'07, March 9, 2007 - March 11, 2007. Porto Alegre, Brazil: Inst. of Elec. and Elec. Eng. Computer Society. pp. 325–330.
- 15.
S Moshavi, E. G Kanterakis and Schilling DL (1996) Multistage linear receivers for DS-CDMA systems. International Journal of Wireless Information Networks.
- 16.
J. M Chaufray, W Hachem and Loubaton P (2004) Asymptotic analysis of optimum and sub-optimum CDMA downlink MMSE receivers. IEEE Transactions on Information Theory: 2620–2638.
- 17.
Chong EKP and Zak SH (2013) An Introduction to Optimization. Wiley.
- 18.
Fong DC-L and Saunders MA (2011) LSMR: An iterative algorithm for sparse least-squares problems. SIAM Journal on Scientific Computing.
- 19. Paige CC, Saunders MA (1982) LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares. ACM Trans Math Softw 8: 43–71.
- 20.
Strang G (2007) Computational Science and Engineering. {Wellesley-Cambridge Press}.
- 21.
Tse D and Viswanath P (2005) Fundamentals of wireless communication. Cambridge University Press. 554 p.
- 22.
Strang G (1986) Introduction to Applied Mathematics. Wellesley-Cambridge Press.