Learning on a Grassmann Manifold:
CSI Quantization for Massive MIMO Systems

Transmit beamforming with receive combining is one of the simplest approaches to achieve full diversity in a MIMO system. It just requires CSI at the transmitter in the form of the transmit beamforming vector. The frequency division duplex (FDD) large-scale MIMO systems cannot utilize channel reciprocity to acquire CSI at the transmitter using uplink transmission. This necessitates channel estimation using downlink pilots and the subsequent feedback of the channel estimates (in this case the beamforming vector) to the transmitter over a dedicated feedback channel with limited capacity. This results in a significant overhead when the number of antennas is large. One way to overcome this problem is to construct a set of beamforming vectors constituting a codebook, which is known to both the transmitter and the receiver. The problem then reduces to determining the best beamforming vector at the receiver and conveying its index to the transmitter over the feedback channel [1]. A key step in this procedure is to construct the codebook, which is a classical problem in MIMO communications [2]. A common feature of all classical works in this direction is the assumption of a statistical channel model (such as Rayleigh) for which the optimal codebooks are constructed to optimize system performance.

With the recent interest in data-driven approaches to wireless system design, it is quite natural to wonder whether machine learning has any role to play in this classical problem. Since the fundamental difficulty in this problem is the dimensionality of the channel, the natural tendency is to think in terms of obtaining a low dimensional representation of the channel using deep learning techniques, such as autoencoders [3], [4], which can be used for codebook construction. An autoencoder operates on the hypothesis that the data possesses a representation on a lower dimensional manifold of the feature space, albeit unknown, and tries to learn the embedded manifold by training over the dataset. In contrast, for MIMO beamforming, the underlying manifold is known to be a Grassmann manifold. This removes the requirement of “learning” the manifold from the dataset which often times can be extremely complicated. Once the manifold is known, we can leverage the “shallow” learning techniques like the clustering algorithms on the manifold to find the optimal codebook for beamforming.

Prior Art. As is the case with any communication theory problem, almost all existing works on limited feedback assume some analytical model for the channel to enable tractable analyses, e.g., i.i.d Rayleigh fading [5], spatial correlation [6], temporal correlation [7] or both [8]. Specifically, the problem of quantized maximum ratio transmission (MRT) beamforming can be interpreted as a Grassmannian line packing problem for both uncorrelated [9] and spatially correlated [10] Rayleigh fading channels and has been extensively studied. The idea of connecting Grassmann manifolds to wireless communications is not new and has been used in other aspects of MIMO systems, such as non-coherent communication [11] and limited feedback unitary precoding [12]. Coming to the context of the limited feedback FDD MIMO, the codebook based on Grassmannian line packing is strictly dependent on the assumption of Rayleigh fading and hence cannot be extended to more realistic scenarios. On the other hand, the discrete Fourier transform (DFT) based beamforming exploits the second order statistics of the channel (such as the direction of departure of the dominant path) and offers a simple yet robust solution to the codebook construction. Owing to the direct connection with the spatial parameters of the channel, the DFT codebook can be extended to the Kronecker product (KP) codebook for 3D beamforming in FD MIMO scenarios. A major drawback of DFT codebook is that it scans all possible directions even though many of them may not be used and thus the available feedback bits are not used efficiently. Finally, since we will be proposing a clustering based solution, it is useful to note that clustering has already found applications in many related problems, such as MIMO detection [13], automatic modulation recognition [14], and radio resource allocation in a heterogeneous network [15].

Contributions. The key technical contribution of this paper lies in the novel formulation of transmit beamforming codebook design for any arbitrary channel distribution as the Grassmannian $K$-means clustering problem. First, we develop the algorithm for $K$-means clustering on the Grassmann manifold that finds the $K$ centroids of the clusters. Leveraging the fact that optimal MRT beamforming vectors lie on a Grassmann manifold, we then develop the design criterion for optimal beamforming codebooks. We then formally establish the connection between the Grassmannian $K$-means algorithm and the codebook design problem and show that the optimal codebook is nothing but the set of centroids given by the $K$-means algorithm. This approach is further extended to develop product codebooks for FD-MIMO systems employing UPA antennas. In particular, we show that under the ${\rm rank}$-$1$ approximation of the channel, the optimal codebook can be decomposed as the Cartesian product of two Grassmannian codebooks of smaller dimensions. We discuss the optimality and performance of the codebooks using both the proposed techniques in terms of average normalized beamforming gain.

Notation. We use boldface small case (upper case) letters, e.g. ${\bf a}(\bf A)$, to designate column vectors (matrices) with entries in ${\mathbb{C}}$. We use ${\mathbb{C}}^{M\times N}$ to represent $M\times N$ dimensional complex space, ${\cal U}(M,N)$ to represent the set of all $M\times N$ orthonormal matrices, ${\cal U}_{M}$ to represent the set of all $M\times M$ unitary matrices. Further, $a^{*}({\bf a}^{*})$ denotes complex conjugate of $a\in{\mathbb{C}}$ $({\bf a}\in{\mathbb{C}}^{M\times 1}$), ${\bf A}^{T}$ denotes transpose, ${\bf A}^{H}$ denotes hermitian, ${\rm svd}({\bf A})$ denotes the singular value decomposition, ${\rm vec}({\bf A})$ denotes the vectorization of a matrix ${\bf A}$. Also, ${\mathbb{E}}_{\bf a}[\cdot]$ represents the expectation over the distribution of ${\bf a}$, $|\cdot|$ denotes the absolute value, $\left\lVert\cdot\right\rVert_{2}$ denotes the matrix two-norm and $j=\sqrt{-1}$.

We consider a narrow-band point-to-point $M_{t}\times M_{r}$ MIMO communication scenario, where the transmitter and receiver are equipped with $M_{t}$ and $M_{r}$ antennas, respectively. In this paper, we focus on the transmit beamforming operation, where the transmitter sends one data stream over a flat fading channel. The discrete-time baseband input-output relation for this system can be expressed as

where ${\bf y}\in\mathbb{C}^{M_{r}\times 1}$ is the received baseband signal, ${\bf H}\in{\mathbb{C}}^{M_{r}\times M_{t}}$ is the block fading MIMO channel, $s\in{\mathbb{C}}$ is the transmitted symbol, ${\bf n}\in{{\mathbb{C}}}^{M_{r}\times 1}$ is the additive noise at the receiver, and ${\bf f}\in{{\mathbb{C}}}^{M_{t}\times 1}$ is the beamforming vector. The symbol energy is given by $\mathbb{E}[|s|^{2}]={\cal E}_{t}$ and the total transmitted energy is $\mathbb{E}[\left\lVert{\bf f}s\right\rVert_{2}^{2}]={\cal E}_{t}\left\lVert{\bf f}\right\rVert_{2}^{2}$. The additive noise ${\bf n}$ is Gaussian, i.e., entries in ${\bf n}$ are i.i.d according to $\mathcal{CN}(0,N_{o})$. It is assumed that perfect channel knowledge is always available at the receiver. With the combining vector ${\bf z}\in{\mathbb{C}}^{M_{r}\times 1}$, the estimated transmitted symbol is obtained as $\hat{s}={\bf z}^{H}{\bf y}$. The receive SNR is

where $\gamma_{t}={\cal E}_{t}\|{\bf f}\|^{2}/N_{o}$ is the transmit SNR. Without loss of generality, it is assumed that $\left\lVert{\bf z}\right\rVert^{2}_{2}=1$. Under this assumption

where ${\Gamma}({\bf f},{\bf z})$ is the effective channel gain or the beamforming gain. The MIMO beamfoming problem is to choose ${\bf f}$ and ${\bf z}$ such that ${\Gamma}({\bf f},{\bf z})$ is maximized, which would in turn maximize the SNR and consequently minimize the average probability of error and maximize the capacity [16]. A receiver that employs maximum ratio combining (MRC) chooses ${\bf z}$ such that ${\Gamma}({\bf f},{\bf z})$ for a given ${\bf f}$ is maximized [9]. Under the assumption that receiver always uses MRC, ${\bf z}$ is given by

and ${\Gamma}({\bf f},{\bf z})$ can be simplified as

Therefore the MIMO beamforming problem is to find the optimal beamforming vector ${\bf f}$ that maximizes $\Gamma({\bf f})$ and can be formally posed as

To constrain transmit power, we assume that $\left\lVert{\bf f}\right\rVert^{2}_{2}=1$ without loss of generality. We consider maximum ratio transmission (MRT), which selects ${\bf f}$ to maximize ${\Gamma}({\bf f},{\bf z})$ for a given ${\bf z}$ [17]. Under the assumptions of MRT, receive MRC, and no other design constraints on ${\bf f}$, for a given $N_{o}$ and ${\cal E}_{t}$, the optimal beamforming vector ${\bf f}$ that maximizes ${\Gamma}$ is

Note that $\operatorname{arg~{}max}$ of any function returns only one out of its possibly many global maximizers and thus the output may not necessarily be unique. For an MRT system, ${\bf f}$ is the orthonormal eigenvector associated with the maximum eigenvalue of ${\bf H}^{H}{\bf H}$ [18]. Let ${\lambda}_{1}\geq\dots\geq{\lambda}_{M_{t}}$ be the eigenvalues of ${\bf H}^{H}{\bf H}$ and ${\bf v}_{1},\dots,{\bf v}_{M_{t}}$ be the corresponding eigenvectors. One possible solution of (5) is ${\bf f}={\bf v}_{1}$ and the corresponding beamforming gain is

For a given ${\bf H}$, let the solution space of (5) be denoted as ${\cal S}_{\bf H}\subset{\cal U}(M_{t},1)$. Then ${\bf v}_{1}\in{\cal S}_{\bf H}$ and for every ${\bf f}\in{\cal S}_{\bf H}$, $\Gamma({\bf f})=\lambda_{1}$.

Quite obviously, MRT beamforming requires CSIT. In particular, in an FDD system, the receiver estimates the channel ${\bf H}$ and sends ${\bf v}_{1}$ back to the transmitter over a feedback channel. Thus the feedback overhead increases as $M_{t}$ increases. Since the feedback channel is typically assumed to be a low-rate reliable channel, it is not always possible to transmit ${\bf v}_{1}$ over this channel without any data compression [1]. One way to model this feedback bottleneck is to assume the feedback channel to be a zero-delay, error-free, and the capacity being limited to $B$ bits per channel use. Thus, it is necessary to introduce some method of quantization for ${\bf v}_{1}$. The most well-known approach for the quantization is to construct a dictionary of beams [1], also known as the beam codebook. In particular, the transmitter and receiver agree upon a finite set of possible beamforming vectors, say ${\cal F}=\{{\bf f}_{1},\dots,{\bf f}_{2^{B}}\}$ of cardinality $2^{B}$. The receiver chooses the appropriate vector ${\bf f}\in{\cal F}$ that maximizes $\Gamma$ and feeds the index of the codeword back to the transmitter. The system-level diagram of a limited feedback FDD-MIMO system, as discussed so far, is provided in Fig. 1.

Therefore for a given codebook $\cal F$, the optimal beamforming vector as stated in (4) is

It is important to note that the original problem of finding the optimal MRT solution for (5) is a constrained optimization problem on the Euclidean space ${\mathbb{C}}^{M_{t}\times 1}$ and does not have unique solution on ${\mathbb{C}}^{M_{t}\times 1}$. This problem can be reformulated as a manifold optimization problem as follows. As argued in [9], it can be shown that the optimal MRT beamformers for every ${\bf H}\in{{\mathbb{C}}}^{M_{r}\times M_{t}}$ lie on a special kind of Riemann manifold embedded in ${\mathbb{C}}^{M_{t}\times 1}$, known as the Grassmann manifold. This will be discussed in Section III. As it will be evident later, this manifold structure of the search domain of ${\bf f}$ in (5) is the key enabler for our data-driven codebook design.

In this section, we provide a brief introduction to the Grassmann manifold, which is instrumental for the design of the proposed beamforming codebook design. The reader is referred to the foundational texts in differential geometry, such as [19], for a comprehensive and rigorous treatment of this manifold. A Grassmann manifold refers to a set of subspaces embedded in a higher-dimensional space (such as the surface of a sphere in $\mathbb{R}^{3}$). More formally, the complex Grassmann manifold ${\cal G}(M_{t},M)$ is defined as

Any element ${\cal Y}$ in ${\cal G}(M_{t},M)$ is typically represented by an orthonormal matrix ${\bf Y}$ whose columns span ${\cal Y}$. It is to be noted that there exists no unique representation of a subspace ${\cal Y}$. This can be explained as follows. Let $\bf Y$ be the orthonormal basis that spans $\cal Y$, then ${\cal Y}$ can also be spanned by some other orthonormal matrix ${\bf Y}^{\prime}={\bf Y}{\bf R}$ for some ${\bf R}\in{\cal U}_{M}$. Thus ${\bf Y}$ and ${\bf Y}^{\prime}$ span the same subspace, which is represented by an equivalence relation ${\bf Y}^{\prime}\equiv{\bf Y}$. Each of these $M$-dimensional linear subspaces can be regarded as a single point on the Grassmann manifold, which is represented by its orthonormal basis. Since a linear subspace can be specified by an arbitrary basis, each point on ${\cal G}(M_{t},M)$ is an equivalence classes of orthonormal matrices. Specifically, ${\bf Y}$ and ${\bf Y}{\bf R}$ correspond to the same point on ${\cal G}(M_{t},M)$.

Now consider the case of $M=1$, i.e. ${\cal G}(M_{t},1)$, which is the set of all one-dimensional subspaces in ${\mathbb{C}}^{M_{t}\times 1}$. In other words, one can visualize ${\cal G}(M_{t},1)$ as the collection of all lines passing through the origin of the space ${\mathbb{C}}^{M_{t}\times 1}$. A line ${\mathcal{L}}$ passing through origin in ${\mathbb{C}}^{M_{t}\times 1}$ is represented in ${\cal G}(M_{t},1)$ by a unit vector ${\bf f}$ that spans the line. It can also be generated by any other unit vector ${\bf f}^{\prime}$ if ${\bf f}^{\prime}\equiv{\bf f}$. Also note, ${\bf f}$ and ${\bf f}^{\prime}$ correspond to the same point on ${\cal G}(M_{t},1)$. Since a complex Grassmann of arbitrary dimensions is difficult to visualize, for illustration purpose, we present the real Grassmann manifold ${\cal G}(3,1)$ in $\mathbb{R}^{3}$ in Fig. 2.

The notion of “distance” between the lines in ${\cal G}(M_{t},1)$ generated by two unit vectors ${\bf f}_{1},{\bf f}_{2}$ can be defined as the sine of the angle between the lines [20]. In particular, the distance is expressed as

The connection between ${\cal G}(M_{t},1)$ and optimal MRT beamforming is established next.

The optimal MRT beamformers are points on ${\cal G}(M_{t},1)$, hence can be described as a point process whose characteristics depend on the underlying channel distribution.

For an arbitrary distribution of ${\bf H}\in{\mathbb{C}}^{M_{r}\times M_{t}}$, the distribution of ${\bf v}_{1}$ will no longer be uniformly distributed on ${\cal G}(M_{t},1)$. As an illustrative example, using the distance function defined in $\eqref{eq::def::distance}$, we compare the Ripley’s $K$ function $K(d)$ [21] of the optimal MRT beamforming vectors on ${\cal G}(M_{t},1)$ for a realistic scenario (see Section VI for more details on the experimental setup) with Rayleigh fading channels for the same system model. Ripley’s $K$ function is a spatial descriptive statistic that measures the deviation of a point process from spatial homogeneity. From Fig. 3, we see that the distribution of the optimal MRT beamforming vectors for the realistic channel is significantly different from the uniform distribution on ${\cal G}(M_{t},1)$ which is equivalent to complete randomness on the manifold. We can also infer that optimal MRT beamformers of the channel for the considered scenario exhibit clustering tendency on ${\cal G}(M_{t},1)$. Therefore, a reasonable codebook construction scheme is to simply deploy an unsupervised clustering method (such as $K$-means clustering) on ${\cal G}(M_{t},1)$ that can identify optimal $K=2^{B}$ cluster centroids and form the codebook $\cal F$. In what follows, we will establish that $K$-means clustering on ${\cal G}(M_{t},1)$ actually yields an optimal codebook.

In this section, we formally establish the connection between Grassmannian $K$-means clustering and the optimal codebook construction. The transmitter and receiver use a $B$-bit codebook ${\cal F}\subset{\cal G}(M_{t},1)$ to map the channel matrix ${\bf H}$ to a codeword in ${\bf f}\in{\cal F}$ according to (7). In order to define the optimality of the codebook, we first introduce the average normalized beamforming gain for ${\cal F}$ as

To measure the average distortion introduced by the quantization using ${\cal F}$, we use the loss in ${\Gamma}_{av}$ as given below:

where $L_{\rm ub}({\cal F})$ is an upper bound of $L({\cal F})$ and the sufficient condition for equality in (16) is ${\rm rank}({\bf H})=1$. The optimal codebook intends to minimize $L({\cal F})$ by minimizing its upper bound $L_{\rm ub}({\cal F})$ as given in (16). Since the current limited feedback approach quantizes ${\bf v}_{1}$ as ${\bf f}$, it is reasonable to minimize $L_{\rm ub}({\cal F})$ which depends only on ${\bf v}_{1}$ and ${\bf f}$. This yields the following codebook design criterion.

Building on this discussion, we now state the method to find the optimal codebook in ${\cal G}(M_{t},1)$ as follows.

Theorem 1 states the equivalence of the optimal codebook design with the $K$-means clustering on ${\cal G}(M_{t},1)$. The benefit of making this connection is that it provides an approach for finding the optimal codebooks leveraging existing work on $K$-means clustering on ${\cal G}(M_{t},1)$. We are now in a position to state the key steps in designing the optimal codebooks based on the Grassmanian $K$-means clustering.

After discussing the general notion of the codebook construction for transmit beamforming for an $M_{t}\times M_{r}$ MIMO system, we focus our attention to a special case of FD MIMO communication. We assume that the transmitter is equipped with a UPA with dimensions $M_{v}\times M_{h}$ ($M_{h}M_{v}=M_{t}$) while the receiver has one antenna, i.e. $M_{r}=1$. Let $\tilde{\bf H}$ represent the $M_{v}\times M_{h}$ channel matrix where the $(i,j)$-th element corresponds to the channel between the antenna element at the $i$-th row and $j$-th column of the UPA and the single receiver antenna at the user. Note that this system model appears as a special case of the general $M_{t}\times M_{r}$ MIMO system discussed in the previous section where ${\bf H}^{T}={\rm vec}(\tilde{\bf H}^{T})$. Hence the codebook can be designed as given in Alg. 2 using the $K$-means clustering in ${\cal G}(M_{v}M_{h},1)$. Assuming $M_{v}=M_{h}=O(n)$, the dimension of the codewords increase as $O(n^{2})$. Naturally, the $K$-means clustering will suffer from the curse of dimensionality as the difference in the maximum and minimum distances between two points in the dataset becomes less prominent as the dimension of the space increases [23]. In this section, we show that the codebook can be obtained by clustering on lower dimensional manifolds by exploring the geometry of the UPA. Considering the UPA channel as a matrix $\tilde{\bf H}$, we have the singular value decomposition of $\tilde{\bf H}$ as follows.

where ${\bf U}$ is the left singular matrix, ${\bf V}$ is the right singular matrix and ${\bf\Sigma}$ is the rectangular diagonal matrix with singular values $\sigma_{i}$ in decreasing order. Let ${\lambda}_{i}$ be the $i$-th eigenvalue of $\tilde{\bf H}^{H}\tilde{\bf H}$, then ${\lambda}_{i}={\sigma}^{2}_{i}$. Further, ${\bf u}_{i}$ and ${\bf v}_{i}$ are the column vectors of ${\bf U}$ and ${\bf V}$ respectively with ${\bf u}^{H}_{i}{\bf u}_{i}=1$ and ${\bf v}^{H}_{i}{\bf v}_{i}=1$. Thus, ${\bf u}_{i}\in{\cal U}(M_{v},1)$ and ${\bf v}_{i}\in{\cal U}(M_{h},1)$. Then we have

From (20), we can represent ${\bf H}$ as the linear combination of ${\bf u}^{T}_{i}\otimes{\bf v}^{H}_{i}$ scaled with $\sigma_{i}$. Thus we have

Due to the finiteness of the physical paths between the transmitter to the receiver, it is well-known that ${\rm rank}({\bf H})<<\min(M_{v},M_{h})$. For the sake of simplicity, we approximate the channel ${\bf H}$ with its dominant direction, i.e. ${\bf u}^{T}_{1}\otimes{\bf v}^{H}_{1}$, which is called ${\rm rank}$-$1$ approximation and the approximated channel $\bar{\bf H}$ is given as

Let ${\bf x}\in{\cal U}(M_{t},1)$ be a beamforming vector for $\bar{\bf H}$. Then the KP form of $\bar{\bf H}$ naturally leads us to the idea of using ${\bf x}$ of the form ${\bf x}={\bf x}_{v}\otimes{\bf x}_{h}$. This motivates us to use separate codebooks ${\cal F}_{h}$ and ${\cal F}_{v}$ for the horizontal and vertical dimensions and enables to design product codebooks by clustering in lower dimensional manifolds. The beamforming gain ${\Gamma}({\bf x})$ for $\bar{\bf H}$ can now be simplified as

where step $(a)$ follows from the fact that $\left\lVert{\bf A}\otimes{\bf B}\right\rVert_{2}=\left\lVert{\bf A}\right\rVert_{2}\left\lVert{\bf B}\right\rVert_{2}$ for two matrices ${\bf A}$ and ${\bf B}$ of any dimensions. The optimal MRT beamforming vector ${\bf f}$ for $\bar{\bf H}$ can be simplified as

where

Observe that one possible solution for optimal MRT beamformer ${\bf f}$ in (23) is given by ${\bf f}_{v}={\bf u}^{*}_{1}$ and ${\bf f}_{h}={\bf v}_{1}$. Following Remark 1, we can argue that ${\bf f}={\bf f}_{v}\otimes{\bf f}_{h}$, where ${\bf f}_{u}\in{\cal G}(M_{v},1)$ and ${\bf f}_{v}\in{\cal G}(M_{h},1)$.

The loss in average normalized beamforming gain ${\Gamma_{av}}$ with the codebook ${\cal F}={\cal F}_{v}\otimes{\cal F}_{h}$ can be bounded as

We will now state the method to construct the product codebook ${\cal F}^{*}$ as follows.

From Lemma 3, it is possible to perform $K$-means clustering independently on ${\cal G}(M_{v},1)$, ${\cal G}(M_{h},1)$ and construct the product codebook with reduced complexity instead of performing $K$-means clustering on ${\cal G}(M_{h}M_{v},1)$. The training and testing procedure of the proposed product codebook design for a given set of channel realizations ${\cal H}$ is given in the following remark.