Microsoft word - limassol_revised.docx

Recovery of a Lattice Generator Matrix from its Gram Matrix for
Feedback and Precoding in MIMO
Francisco A. Monteiro, Student Member, IEEE, and Ian J. Wassell
Abstract— Either in communication or in control applications,
coding, MIMO spatial multiplexing, and even OFDM) multiple-input multiple-output systems often assume the
unified from a lattice perspective as a general equalization knowledge of a matrix that relates the input and output vectors.
problem (e.g., [14]). Advances in lattice theory are therefore For discrete inputs, this linear transformation generates a
multidimensional lattice. The same lattice may be described by
an infinite number of generator matrixes, even if the rotated
There are several ways of describing a lattice (e.g., via versions of a lattice are not considered. While obtaining the
modular equations [15] or trellis structures [16]), however, Gram matrix from a given generator matrix is a trivial
the two most popular ones in engineering applications are i) operation, the converse is not obvious for non-square matrixes
the generator matrix and ii) the Gram matrix. The and is a research topic in algorithmic number theory. This
computation of the latter given the former is trivial. The paper proposes a method to execute such a conversion and
reverse is not, and an efficient algorithm for this conversion applies it in a novel MIMO system implementation where some
remains an open problem in the theory of lattices. of the complexity is taken from the receiver to the transmitter.
It should be noticed that an efficient algorithm for this Additionally, given the symmetry of the Gram matrix, the
reverse operation can allow a lattice to be described using number of elements required in the feedback channel is nearly
only about half the number of elements usually required when the dimensionality of the space is sufficiently high, provided that the Gram matrix is always symmetric. For Any multiple-input multiple-output (MIMO) system is example, in MIMO communications with channel state traditionally described by a generator matrix. In the wireless information at the transmitter (CSIT), this means that about (and recently also in wired [1],[2]) communications systems half the number of coefficients would need to be sent to the context, the matrix storing the fading coefficients between transmitter (Tx) when compared with that when using transmit and receive antennas is known as the channel traditional feedback [17]. Using the traditional example in matrix, however in other contexts which operate with [17] , while in a single-input single-output configuration vectorial spaces, the matrix receives other names. (with BPSK modulation) the channel state information is Considering that the inputs are restricted to a set of discrete conveyed by one coefficient only, in a 4×4 antenna system inputs isomorphic to , these systems can be framed in the one has 16 complex variables describing the channel, or equivalently 32 real coefficients, that need to be periodically The regularity of a lattice lends itself to the representation fedback to the transmitter. In fact, the number of coefficients of problems where different signals are interpreted as a point to be fedback is the product of the number of antennas at the in a multidimensional space. They appear in many areas of transmitter, at the receiver (Rx), the delay spread and, in signal processing such as quantization[3][4][5] or image multi-user environments, also proportional to the product processing [6]. Recently, lattices have also become a central with the number of users. tool in cryptography [7] [8]; they are also used in numerical This paper shows how an approximate solution to an open integration (i.e., quadrature) of multi-dimensional functions problem in algorithmic number theory may lead to a more constituting lattice rules [9][10], and have a long history in efficient CSIT mechanism. The paper proposes an algorithm the fields of geometry of numbers, algorithmic number to obtain a close approximation for a generator matrix given theory [11], multidimensional sphere packing (important in a Gram matrix of a lattice. The algorithm is based on an coding theory) [12] and also in integer programming [13]. exact technique recently proposed by Lenstra [11] (an The communication theory community has recently seen historical figure in the fields of algorithms for lattices). This topics that were thought to be distinct (such as the multiple paper uses the proposed algorithm as a constituent block in a access channel, the broadcast channel, precoding, space-time novel strategy for closed-loop MIMO communication. Manuscript received November 23, 2009. This work was supported in A lattice is a discrete subgroup (of maximal rank) in a part by a scholarship from the Foundation for Science and Technology, Euclidean space and can be defined in a number of ways, as listed in Section I. We summarise here the most common Francisco A. Monteiro is with the Department of Engineering and with The Computer Laboratory, University of Cambridge, UK, and also with the Telecommunications Institute at the Lisbon University Institute, Portugal Ian J. Wassell is with The Computer Laboratory, University of Cambridge, UK (e-mail: [email protected]). Revised version of the paper in the ISCCSP 2010 proceedings: a QR is moved into the receiver (Fig.3) and the implications from that. Presented at the Int. Symposium on Communications, Control and Signal Processing, Limassol, Cyprus, March 2010. (IEEE Signal Processing Society.) where y are the points of the lattice, hi are the generating
vectors where each corresponds to the ith column of the n×n generator matrix H (considering full-rank lattices only).
Consequently, one can state that G induces a quadratic
Each integer xi is an element of the column vectors x. Thus, form and is definite positive because
a lattice defined as in (1) is the span of the column space of This permits us to say that always has a LDLT
the generator matrix H, when we restrict the input to integers. decomposition [21][20][22].
Note that the prevalent notation in MIMO literature Obtaining a valid from is not simple. defines an considers column vectors while in channel coding or in other abstract lattice, however, two versions of a lattice will have fields in mathematics lattices are traditionally represented by the same Gram matrix and in general, for a given , the span of the row space of a generator matrix. Notice that rows and columns of a given H span different lattices.
can be transformed into one factorization problem. When representing an equivalent lattice defined by decomposition offers a good solution as it applies to symmetric definite positive matrices [21]. For the general m×n case, obtaining a basis from a specified Gram matrix had no available method in the literature until recently [11]. is an unitary matrix (with real elements and is a unimodular matrix (with C. The volume of lattices Full rank lattices are specified by a full-rank generator matrix and the volume of a lattice (e.g., [8]) is given by With this in mind, the unitary transformation performs a rigid rotation of the lattice structure (i.e., of its generating vectors), while the unimodular matrix replaces a set of is rank-deficient (which is the case when generating vectors by a different set that still generates the non-square), the volume is One of the hardest lattice problems is the lattice distinguishing problem, i.e., to discover if two lattices are For a traditional complex representation with N and NR antennas as outputs, the received signal is question becomes trivial. But when both transformations are unknown the question is difficult to solve in some particular problems [18],[19]. This decision problem has a simple solution when the lattices are rational lattices (when all entries are in ). In that case two lattices are equivalent if and only if their generating matrixes have the same Hermite Normal Form [13],[20]. However, the real lattices that arise mean circularly symmetric Gaussian random variable with in communication problems lead to numerical problems given the large numerators and denominators in the fractions unitary variance. The noise vector is representing fading coefficients. In that case the best approach is to use the fact that the QR decomposition is with independent circularly symmetric Gaussian unique up to signs in the main diagonal. random variables, each one with a certain variance In the remainder of the paper we will resort to the equivalent real model of complex lattices: where H is the Hermitian operator (conjugate and transpose). between all generating vectors and thus is unique to a lattice subject to unitary transformations (albeit not unique for unimodular transformations should be noticed that, by construction, symmetric (because the inner product is commutative) and a where L is a rational n×n lower triangular matrix with ones
definite positive matrix. This second property can be verified in the diagonal (i.e., is a unit matrix) and D is a n×n diagonal
from the squared Euclidean norm of y (using the Hermitian matrix with rational diagonal entries
Presented at the Int. Symposium on Communications, Control and Signal Processing, Limassol, Cyprus, March 2010. (IEEE Signal Processing Society.) number of squares of R rational numbers, that is, Using traditional singular value decomposition (SVD) An exact expansion of these djj can be accomplished by applying a naive greedy algorithm as proposed for the first time by Lenstra in [11]. Imposing an exact expansion for each often leads to a large number of terms in the sum where is a diagonal matrix and (10) and for that reason Lenstra also proposed the use of a matrices (i.e., norm-preserving rotations, and therefore randomized algorithm given in [23], which assures the preserves the statistics of the noise term). A SVD-based bound scheme implies one SVD decomposition (requiring at least This paper proposes to replace an exact conversion from flops [22]) at the Rx in addition to matrix by an approximate conversion (leading to a using a fixed complexity algorithm that can be applied in a requiring flops). This technique achieves capacity real time communication system. Based on the results in [23], through water filling power allocation (according to the we use a simple greedy algorithm for the expansion and singular values) [26]. truncate the number of terms to In [27] it was shown that the LDLT decomposition
truncated Lenstra algorithm. One way of achieving this is by achieves better performance than standard SVD, while being using R equal terms in (10). One may notice that when R=1, slightly less complex. Most importantly, that new approach the algorithm resorts to an approximated Cholesky takes advantage of having a precoding matrix with zero elements. In fact it requires a in the One starts by constructing a tall matrix rows and n columns. For the case with R=4 terms for each of triangular matrix is fedback from the R This paper proposes a technique that achieves the same performance as [27] while removing most of the complexity from the receiver side to the transmitter side, which is an important feature in scenarios where the transmitter is a base station and the receiver terminal should be made as simple as possible, i.e., by avoiding expensive processing. where each row has one and only one non-zero entry. Now, Remark: as in [27], this paper is not assessing the one can re-construct the diagonal matrix from using capacity-achieving regime and thus, for simplicity, uniform power is allocated to the transmit antennas. Both this proposal and [27] have a pre-processing stage at We have made this matrix multiplication explicit to Rx consisting of the generation of a definite positive matrix emphasise how this ensures that each djj is a sum of squares G, the Gram matrix of the lattice defined by the columns of
as defined in (10). Finally, the approximated generator . This Gram matrix is formed by the left multiplication (3) In this proposal it is imperative CSIT so that Tx can construct the precoding matrix . This paper shows that his can be achieved with the feedback of a lower triangular matrix only. Given the symmetry of , the Tx only needs to reconstruct the entire matrix, achieving the same bandwidth savings seen in [27] for the feedback channel. After The complexity of this technique is cubic in the reconstructing the entire (by symmetry), the Tx can use dimension n, due to the LDLT steps, to which we should add the truncated Lenstra algorithm described in Section IV to
for the rational approximation steps. The overall obtain an equivalent generator matrix (Section II) for the , however, as it will be shown lattice. This matrix, later in Table 1, as the LDLT decomposition will be reused, equivalent generator matrix for the lattice, holding the same
only the n term will add to the complexity of the technique Gram matrix. However, it is possible to obtain from them the same and unique generator matrix resulting from QR It should be noticed that, unlike Cholesky decomposition, decompositions remembering that a QR decomposition is this technique is applicable to both square and non-square unique when imposing the positiveness of elements in the matrixes, allowing us to retrieve a rectangular from . Presented at the Int. Symposium on Communications, Control and Signal Processing, Limassol, Cyprus, March 2010. (IEEE Signal Processing Society.) independent transmission channels and ii) geometrically it corresponds to a communication problem over a rectangular lead to and , which would be the same matrix (up signs lattice. Thus, it is convenient to think of a lattice as the result in main diagonal) if there was no distortion associated with of a linear transformation of the cubic lattice in the truncated Lenstra algorithm. A central aspect is that the same Gram matrix is also obtainable from alone, alone or even a mixture of both, given their closeness: orthogonal generating vectors which span a rectangular lattice (this lattice would even have the simplest trellis representation one may have for lattices, e.g., [16]). The As indicated in Section II.B and in Section IV, would performance increase can be geometrically interpreted from have a LDLT decomposition, which can be calculated not this insight. A rectangular lattice is obtained from a
only given
(in both cases applying (3)) but also deformation of a cubic lattice , or both. However, this will not be the dimension according to each matrix to be LDLT decomposed.
rectangles and thus even a zero-forcing detector experiences Taking advantage of these facts the mode in (7) and be no performance penalty. The right multiplication of the channel matrix by (17) changes the power at the transmitter. The geometric interpretation is also useful on this matter. The “row lattice” The matrixes used in (18) will be presented and justified on the fallowing. First, notice that this made a matrix to appear (a permutation matrix may be needed to have a unique QR), which, despite not being the Gram matrix of the underlying lattice, it is the (approximate) Gram matrix of the lattice spanned by the row Subsequently, one also needs the insertion of a diagonal lattice (as indicated in Section II). This matrix also has an LDLT decomposition and thus (18) can equivalently be scaling
at the precoding stage so that the volume of both lattices underlying the transmission scheme becomes Figure 1 depicts the overall transmission scheme that is proposed while in Figure 2 and in Figure 3 one can observe in detail the processing required respectively at the T Finally, after the detection filter at the receiver, the entire x as well as the fluxes of CSI between both of them. At the Rx it is important to highlight that there are two parallel processing occurring at different stages and each one associated with a different fading block: i) obtain G that will
be sent back to Tx in the form of a triangular matrix and ii) construct the receive filter from a received strictly upper triangular matrix and Q. In fact,
triangular but also a unit lower triangular (ones in the It should be noticed that, as Q is orthogonal (unitary if diagonal). This saves the transmission of the diagonal and
further simplifies the computations at the receiver. The R be forwarded to the Rx. These coefficients are denoted by . The process is summarised in Algorithm 1. (The will then just have to apply the filtering to the channel is assumed to remain unchanged between adjacent incoming precoded signal, i.e., the unavoidable filtering symbols as it is common in the slow fading assumption.) multiplications that are present in all detectors. Besides that, the Rx only needs to compute G and (given its symmetry)
send back to the Tx only the lower or the upper parts of G,
which will be denoted by
are computed and sent from the Tx to the Rx. The resulting transmission chain (20) can be interpreted in two ways: i) algebraically it corresponds to a set of Figure 1: Proposed closed loop transmission scheme. Presented at the Int. Symposium on Communications, Control and Signal Processing, Limassol, Cyprus, March 2010. (IEEE Signal Processing Society.) coefficients flowing in both the uplink and downlink. The number of operations in Table 1 is presented in a way that shows the contribution of each individual processing stage to the total number of operations of the Rx or Tx (matrix complexity at the receiver comes from a QR decomposition and two matrix multiplications: one to initially obtain (similar to [27]) and then the unavoidable filtering Figure 2: Processing at the transmitter. multiplication by . One should remember that this last multiplication is common to all types of receivers in both To access the approximation one first computes the error matrix of the Gram matrix involved (i.e., the Gram matrix associated with the “row lattice”, as indicated in Section V) 5: Obtain approximate from using the algorithm and one applies to it the squared Frobenius matrix norm [22] 7: Compute the Gram matrix of the “row lattice” at Tx: Figure 4 shows the distribution of this error for three example cases having the number of real dimensions most common in MIMO wireless communications (and with (note: for a non-squared the non-zero rows must be variance 0.5 per real component). Notice that despite the Gram matrix of the “row lattice” 10: Strictly lower triangular matrix is sent: and the one of “column lattice” being different, they hold the statistics and consequently they are interchangeable in (3). (note: can be computed at the same time as steps 4-10) For a NT =4, NR =4 configuration (i.e., n=8 dimensions) under a Rayleigh fading channel and using 16-QAM modulation, it was verified that with the LDLT
multiplies the received decomposition proposed in this paper the error shown in Figure 4 leads to a negligible performance penalty in terms of symbol error rate (SER) in respect to the results presented The number of flops required by the LDLT decomposition in [27] for the same configuration when using the same
, which is half of the number of flops needed in minimum mean squared error (MMSE) receiver. Gaussian elimination, the number of flops of QR This paper shows how to reconstruct (with very low more efficient algorithms for matrix multiplication). Table 1 distortion and fixed complexity) a generator matrix of a contains a comparison of the proposed technique with SVD lattice from one given Gram matrix of the same lattice for and with [27] in terms of the number of flops and number of non-square matrixes. This opens new possibilities in several problems of engineering and computer science that rely on Presented at the Int. Symposium on Communications, Control and Signal Processing, Limassol, Cyprus, March 2010. (IEEE Signal Processing Society.) lattice geometry as it breaks through the restriction that the [8] Daniele Micciancio and Shafi Goldwasser, Complexity of Lattice Cholesky decompositions imposes (valid for squared Problems - A Cryptographic Perspective. Norwell, Massachusetts, matrixes). Subsequently, the paper shows how the algorithm devised in Section IV can be central to a technique for [9] Ian H. Sloan and Stephen Joe, Lattice Methods for Multiple Integration. Oxford, UK: Oxford University Press, 1994. channel diagonalisation of MIMO systems. With this [10] J. N. Lyness, "An introduction to lattice rules and their generator technique: i) LDLT decomposition takes place at the transmit
matrices," IMA Journal of Numerical Analysis - Oxford University side; ii) the number of elements to be fedback to T Press, vol. 9, no. 3, pp. 405-419, July 1989. , as in [27]; iii) the filtering matrix at R [11] Hendrik W. Lenstra, "Lattices," in Algorithmic Number Theory, J. P. from a unit lower triangular and an orthogonal matrix, which Buhler and P. Stevenhagen, Eds. Cambridge, UK: Cambridge further reduces the complexity of the filtering matrix [12] John H. Conway and Neil J. A. Sloane, Sphere Packings, Lattices and multiplication at Rx. The extra cost to bear is a QR Groups, 3rd ed. New York, New York, USA: Springer, 1999. decomposition at the Rx. However, a QR module would have [13] Alexandre Schrijver, Theory of Linear and Integer Programming. to exist at Rx if typical open-loop spatial multiplexing Chischester, UK: John Wiley & Sons, 1986, ch. 4, 5, 6. schemes are also to be supported. For large number of [14] Wei Zhang, Xiaoli Ma, B. Gestner, and D. Anderson, "Designing low- antennas, the presented closed loop architecture (i.e., with complexity equalizers for wireless systems," IEEE Communications CSIT) for MIMO communications nearly halves the number , vol. 47, no. 1, pp. 56-62, January 2009. of coefficients traditionally needed to represent the channel. [15] A. Paz and C. P. Schnorr, "Approximating integer lattices by lattices with cycle factor groups," in Proceedings of 14th Int Conf on Automata, Languages and Programming, Karlsruhe, Germany, LNCS [16] G. David Forney, "Density / length profiles and trellis complexity of lattices," IEEE Transactions on Information Theory, vol. 40, no. 6, pp. [17] David J. Love, Robert W. Heath, Wiroonsak Santipach, and Michael L. Honig, "What is the value of limited feedback for MIMO channels," IEEE Communications Magazine, vol. 42, no. 10, pp. 54-59, October [18] Michael Szydlo, "Hypercubic lattice reduction and analysis of GGH and NTRU signatures," in Proceedings of Eurocrypt 2003, Warsaw, Poland, LNCS 2656, Germany, 2003, pp. 433-448. [19] Erik Agrell, Alexander Vardy Thomas Eriksoon, and Kenneth Zeger, "Closest point in lattices," IEEE Transactions on Information Theory, vol. 48, no. 8, pp. 2201-2214, August 2002. [20] Robert Piziak and P. L. Odell, Matrix Theory - From Generalized Figure 4: Probability distribution of the squared Frobenius norm of the error Inverses to Jordan Form. Boca Raton, FL: Chapman & Hall - CRC, [21] G. W. Stewart, Introduction to Matrix Computations. London, UK: [1] Fernando Pérez-Cruz, Miguel R. Rodrigues, and Sergio Verdú, [22] Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd "Optimal precoding for digital subscriber lines," in Proceedings of ed. Baltimore, Maryland, USA: The Hohns Hopkins University Press, ICC'08 - The IEEE Inter. Conf. on Communications, Beijing, May [23] M. O. Rabin and J. O. Shallit, "Randomized algorithms in number [2] Per Ödlig, Thomas Magesacher, Per Ola Börjesson Stefan öst, Miguel theory," Communications on Pure and Applied Mathematics, vol. Berg, and Enrique Areizaga, "The forth generation broadband concept," IEEE Communications Magazine, vol. 43, no. 1, pp. 63-69, [24] Jürgen Lindner, "Transmission over MIMO channels: on diversiy and spacial multiplexing," in Proceedings of ISCTA´07 - The Inter. [3] M. Vedat Eyuboglu and G. David Forney, "Lattice and trellis Symposium on Communication Theory and Applications, Ambleside, quantization with lattice- and trellis-bounded codebooks - high-rate theory for memoryless sources," IEEE Transactions on Information [25] Kenichi Kobayashi, Tomoaki Ohtsuki, and Toshinobu Kaneko, theory, vol. 39, no. 1, pp. 46-58, January 1993. "MIMO Systems in the Presence of Feedback Delay," IEICE [4] Erik Agrell and Thomas Eriksson, "Optimization of lattices for Transactions on Communications, vol. E91-B, no. 3, pp. 829-836, quantization," IEEE Transactions on Information Theory, vol. 44, no. [26] Ezio Biglieri and Giorgio Taricco, Transmission and Reception with [5] Robert M. Gray and David L. Neuhoff, "Quantization," IEEE Transactions on Information theory, vol. 44, no. 6, pp. 2325-2383, Massachusetts, USA: now Publishers, 2004. [27] Che-Chen Chou, Hsi-Chei Chen, and Jen-Ming Wu, "A low [6] R. Cortelazzo and G. Manduchi, "On the determinant of all sublattices complexity channel decomposition and feedback strategy for MIMO of preassigned index and its applications to multidimensional precoder design," in Proc. of ICASSP'09 - The IEEE Int. Conf. on sampling," IEEE Transactions on Circuits and Systems for Video Acoustics, Speech and Signal Processing, Taipei, Taiwan, April 2009, Technology, vol. 3, no. 4, pp. 318-320, August 1993. [7] Daniele Micciancio and Oded Regev, "Lattice-based cryptography," in [28] Ran Raz, "On the complexity of matrix product," in Proceedings of the Post-Quantum Cryptography, Daniel J. Bernstein, Johannes thiry-fourth annual ACM symposium on Theory of computing, Buchmann, and Erik Dahmen, Eds. Berlin, Germany: Springer, 2009, Montreal, Canada, May 2002, pp. 144-151. Presented at the Int. Symposium on Communications, Control and Signal Processing, Limassol, Cyprus, March 2010. (IEEE Signal Processing Society.)

Source: http://iul.pt/~frmo/ISCCSP_2010_revised.pdf