Xi'an Jiao Tong University, Xi'an, China

NEC Labs America, Princeton, NJ, 08540, USA

Electrical Engineering Department, Columbia University, New York, NY, 10027, USA

Abstract

We consider a large-scale MIMO system operating in the 60 GHz band employing beamforming for high-speed data transmission. We assume that the number of RF chains is smaller than the number of antennas, which motivates the use of antenna selection to exploit the beamforming gain afforded by the large-scale antenna array. However, the system constraint that at the receiver, only a linear combination of the receive antenna outputs is available, which together with the large dimension of the MIMO system makes it challenging to devise an efficient antenna selection algorithm. By exploiting the strong line-of-sight property of the 60 GHz channels, we propose an iterative antenna selection algorithm based on discrete stochastic approximation that can quickly lock onto a near-optimal antenna subset. Moreover, given a selected antenna subset, we propose an adaptive transmit and receive beamforming algorithm based on the stochastic gradient method that makes use of a low-rate feedback channel to inform the transmitter about the selected beams. Simulation results show that both the proposed antenna selection and the adaptive beamforming techniques exhibit fast convergence and near-optimal performance.

1 Introduction

The 60 GHz millimeter wave communication has received significant recent attention, and it is considered as a promising technology for short-range broadband wireless transmission with data rate up to multi-giga bits/s

To reduce the hardware complexity, typically, the number of radio-frequency (RF) chains employed (consisting of amplifiers, AD/DA converters, mixers, etc.) is smaller than the number of antenna elements, and the antenna selection technique is used to fully exploit the beamforming gain afforded by the large-scale MIMO antennas. Although various schemes for antenna selection exist in the literature

The remainder of this paper is organized as follows. The system under consideration and the problems of antenna selection and beamformer adaptation are described in Section 2. The proposed antenna selection algorithm is developed in Section 3. The proposed transmit and receive adaptive beamforming algorithm is presented in Section 4. Simulation results are provided in Section 5. Finally Section 6 concludes the paper.

2 System description and problem formulation

Consider a typical indoor communication scenario and a MIMO system with _{t }
_{r }

A typical indoor communication scenario and channel modeling using ray tracing

**A typical indoor communication scenario and channel modeling using ray tracing**.

where ^{(i)}, ^{(i)},

denotes the cluster constitution by rays therein, where ^{(i,k)}, ^{(i,k)},

In OFDM-based systems, the narrowband subchannels are assumed to be flat fading. Thus, the equivalent channel matrix between the transmitter and receiver is given by

for _{r }
_{t}
_{ij }
_{rays }traced rays between them at the delay of the LOS component, _{0}; and **
H
**

where the Rician

We assume that the numbers of transmit and receive antennas, i.e., _{t }
_{r }
_{t }
_{r}
_{t }
_{t }
_{r }
_{r}
_{t }× n_{r }
_{t }× N_{r }
_{t }
_{r }
**
H
**

A 60 GHz MIMO system employing antenna selection and transmit/receive beamforming

**A 60 GHz MIMO system employing antenna selection and transmit/receive beamforming**.

For data transmission over the chosen MIMO system **
H
**

where _{s }
_{0 }are the symbol energy and noise power density, respectively; **
u
**|| = 1, is applied to the received signal

For a given antenna subset **
H
**

One variation to the above antenna selection problem is that instead of the numbers of available RF chains (_{t}
_{r}
_{1 }≥

Problem statement

Our problem is to compute the optimal antenna set **
w
**and

In this paper, we propose a two-stage solution to the above problem of joint antenna selection and transmit-receive beamformer adaptation. In the first stage, we employ a discrete stochastic approximation algorithm to perform antenna selection. By setting the transmit and receive beamformers to some specific values, this method computes a bound on the principal singular value of **
H
**

In the next two sections, we discuss the detailed algorithms for antenna selection and beamformer adaptation, respectively.

3 Antenna selection using stochastic approximation and Gerschgorin circle

3.1 The stochastic approximation algorithm

As mentioned earlier, we can only observe **w**
**u**
**
H
**

In **
π
**, which indicates an estimate of the occupation probability of one state (i.e., antenna subset). Under certain conditions, such an algorithm converges to the state that has the largest occupation probability in

Due to the potentially large search space in the present problem, which not only limits the convergence speed but also makes it difficult to maintain the occupation probability vector, the algorithms in **
H
**

Specifically, we start with an initial antenna subset ^{(0) }and an occupation probability vector ^{(0) }= [^{(0)}, 1]^{T}
_{t }
_{r }
_{t }
_{r }

Instead of keeping records for all candidates, we dynamically allocate and maintain record in **
π
**for the new subset found in each iteration. If a subset already has a record in

We replace the selected subset with the current subset if the current subset has a larger occupation probabilities in **π**. Otherwise, keep the selected subset unchanged, thus completes one iteration.

In general, the convergence is achieved when the number of iterations goes to infinity. In practice, when it happens that one subset is selected in a large number, say 100, consecutive iterations, the algorithm is regarded as convergent and terminated, and the last selected subset is the global (sub)optimizer. Since most of the evaluations and decisions are generally made at the receiver, a low-rate and error-free feedback channel is assumed to coordinate the transmitter via feedback information. In each subiteration, the transmitter should know in advance which transmit antennas have been left in the current subset (i.e., ^{(n)}) from last subiteration (because the current subset might have been changed in the previous subiteration), and then could generate a new subset by replacing the one with a random transmit antenna outside ^{(n)}. Without feedback an invalid situation might happen such that a transmit antenna, which is already assigned to one RF chain in the current subset, is selected again for another RF chain. In other words, feedback is necessary only in subiterations in which the current subset has changed for the transmit antennas during the last update in the previous subiteration. This implies that the amount of feedbacks is rather limited.

The modified stochastic approximation algorithm for antenna selection is summarized in Algorithm 1. In what follows we discuss the form of the objective function

3.2 Estimating the principal singular value using Gerschgorin circle

The Gerschgorin circle theorem

Denote the channel submatrix of the selected antenna subset by _{r }
**
H
**

Denote the eigenvalues of **
R
**

with the radius of the

The above **
R
**

An illustration of the Gerschgorin circle

**An illustration of the Gerschgorin circle**.

Since the principal singular value _{1 }of **
H
**

Note that, _{1 }is the maximum over the λ_{1 }norms of the rows of **
R
**

Next we prove a lemma that provides a useful bound on _{1 }and _{1}.

**Lemma 1 **
**U**
^{H}
**U **
**
I
**,

_{ij}

To prove the lemma, we define

where the last inequality follows upon noting the positive semi-definite ordering _{t}

Further, we have

Combining (18) with (19) we have the desired result.

In our problem, only the receive beamformer output **w**
**u**
_{1}, _{1 }given in the right-hand side (RHS) of (15) in the following way. For each transmit antenna in the subset _{t}

respectively, where **
e
**

We now use the following expression to approximately lower bound _{1}, _{1}.

Substituting (20) into (21), we have

Note that in the noiseless case, we have that _{2 }in (22) is equal to

Then, using Lemma 1 and its proof, we see that _{1 }as well as _{1}(**
R
**

In order to mitigate the noise, for each transmit beamformer **
e
**

The final estimator of the lower bound on the principal eigenvalue of **
R
**

It is easily seen that both the 1st-order and 2nd-order noise terms are averaged out in

Recall that in the stochastic approximation algorithm for antenna selection, at each iteration, we sequentially update the transmit and receive antennas and compute the corresponding objective functions. The above approach for calculating the objective function fits naturally in this framework, since for each transmit antenna candidate, we only need to transmit a pilot signal from it and then compute the corresponding

**
H
**

**
u
**

or its smoother version

where

Finally, we note that for a given _{t}
_{r}

4 Adaptive Tx/Rx beamforming with low-rate feedback

Once the antenna subset **
H
**

Since the channel matrix **
H
**

4.1 Stochastic gradient algorithm for beamformer update

The algorithm for the beamformer update is a generalization of **
w
**,

**Algorithm 1 **Adaptive antenna selection using stochastic approximation and G-circle

INITIALIZATION:

Select initial antenna subset ^{(0) }and set **
π
**

Transmit pilot signals from each selected transmit antenna and obtain the received signals using the selected receive antennas {^{(m)}, _{t }
_{r}

Compute the objective function ^{(0)}) using (24)-(25);

Set selected antenna subset

For

For _{t }
_{r}

SAMPLING AND EVALUATION:

Replace the ^{(n) }by a randomly selected antenna that is not in ^{(n) }to obtain a new subset ^{(n) }by only one element;

For a newly selected transmit antenna, transmit pilot signals from it and obtain the received signals {^{(m)},

For a newly selected receive antenna, sequentially transmit pilot signals from all transmit antennas and obtain the received signals;

Recalculate the objective function

ACCEPTANCE:

If

Update

If **
π
**Then

Append the column **
π
**;

EndIf

Feed back ^{(n) }if the update affects any transmit antenna therein

EndIf

ADAPTIVE FILTERING:

Set forgetting factor:

**
π
**

^{(n)}(^{(n)}) = ^{(n)}(^{(n)}) +

EndFor (

SELECTION:

If

Set

EndIf

^{(n+1) }= ^{(n)}; **
π
**

EndFor (

where ^{2 }are measured, and the effective channel gain ^{H}H_{ω}w|^{2 }can be used as a performance metric independent of transmit power. Finally, the beamformers are updated using the perturbation vector pair that gives the largest output power at the receiver. The transmitter is informed about the selected perturbation vector by a ⌈log _{t}

**Algorithm 2 **Stochastic gradient algorithm for beamformer update

INITIALIZATION:

Initialize **
w
**

For

PROBING:

Generate _{t }
_{r }
**
w
**

Evaluate the received power ^{2 }for each one of the _{t}K_{r }

UPDATE AND FEEDBACK:

Let **
p
**

Feedback the index of the best transmit perturbation vector using _{t}

Update the beamformers:

EndFor

4.2 Implementation issues

We next discuss some implementation issues related to the above stochastic gradient algorithm for beamformer update.

Initialization

A good initialization can considerably speed up the convergence of the above stochastic gradient algorithm compared with random initialization. For the application considered in this paper, recall that the channel consists of a deterministic LOS component **
H
**

Parameterization

Since both **
w
**and

Given the vector **
v
**or equivalently

where _{i}
_{i}
_{t }
_{i}

Parallel reception

Since at each iteration, the best beamformer pair is chosen out of _{t}K_{r }
^{2}, it would require _{t}K_{r }
_{r }
_{r }
_{t }

Conservative update

If all candidate _{t }
_{r }
_{t }
_{r }

5 Simulation results

We consider an empty conference room with dimension 4m(L) × 3m(W) × 3m(H) for analysis, in which a large-scale MIMO system with _{t }
_{r }
_{t }
_{r }

Performance of antenna selection with fixed size

The performance of Algorithm 1 for antenna selection in a single run is shown in Figure

A single-run performance of Algorithm 1 for antenna selection

**A single-run performance of Algorithm 1 for antenna selection**.

The average performance (over 100 runs) of Algorithm 1 for antenna selection

**The average performance (over 100 runs) of Algorithm 1 for antenna selection**.

Performance of antenna selection with variable size

Figure _{t}
_{1 }≥ 0.05, we backup the current parameters (i.e., current iteration number, selected subset, probability vector, etc.), and then terminate the current iteration and set _{t }
_{t }
_{t }
_{t }

Performance of the antenna selection algorithm with variable size

**Performance of the antenna selection algorithm with variable size**.

Size of the selected antenna subset by the antenna selection algorithm with variable size

**Size of the selected antenna subset by the antenna selection algorithm with variable size**.

Performance of adaptive beamforming

Figure _{t }
_{r }
_{t }
_{r }
_{t }
_{r}

A single-run performance of Algorithm 2 for adaptive transmit/receive beamforming

**A single-run performance of Algorithm 2 for adaptive transmit/receive beamforming**.

Performance of Algorithm 2 with different feedback bits

**Performance of Algorithm 2 with different feedback bits**.

Overall performance of adaptive antenna selection and beamforming

The effective channel gain, ^{H}H_{ω}w|^{2}, is a metric indicating the overall performance by associating the adaptive antenna selection with beamforming. In this simulation, the transceiver is dropped at 100 random locations with minimum distance 30 cm in the room independently, and we generate the channel realizations therein using 3-D ray-tracing technique. By running the proposed adaptive algorithms for these drops, Figure

Overall performance for Algorithm 1 and 2

**Overall performance for Algorithm 1 and 2**. Average over 100 random Tx/Rx locations and channel realizations.

6 Conclusions

We have proposed a sequential antenna selection algorithm and an adaptive transmit/receive beamforming algorithm for large-scale MIMO systems in the 60 GHz band. One constraint of the system under consideration is that the receiver can only access a linear combination of the receive antenna outputs, which makes the traditional antenna selection schemes based on the channel matrix not applicable. The proposed antenna selection method uses a bound on the largest singular value of the channel matrix based on the Gerschgorin circle. The method is particularly useful over the 60 GHz channel, which has a strong line-of-sight component, and it employs a discrete stochastic approximation technique to quickly lock onto a near-optimal antenna subset. We have also proposed an adaptive joint transmit and receive beamforming technique based on the stochastic gradient method that makes use of a low-rate feedback channel to inform the transmitter about the selected beam. Simulation results show that both the proposed antenna selection and the adaptive beamforming techniques exhibit fast convergence and near-optimal performance.

Competing interests

The authors declare that they have no competing interests.

Note

^{1}Note that in obtaining (20) without loss of generality we have absorbed **
H
**.

Acknowledgements

The authors wish to acknowledge financial support from the National Key Specialized Project of China (2009ZX03003-008-02) and the National Science Foundation of China (60902043).