Analog Beamforming for Millimeter-Wave MIMO Systems via Stochastic Optimization Ying Zou, Qiang Li, Gang Yang, and Xiaotao Cheng Email: 201521260145@std.uestc.edu.cn, {liqiang, yanggang}@uestc.edu.cn, xiantaocheng@163.com University of Electronic Science and Technology of China, Chengdu, China. Abstract—Millimeter-wave system is promising to enhance the data rate of wireless communications, due to abundant frequency spectrum available, while it suffers from large path loss. The codebook-based beamforming is widely used to compensate the severe channel attenuation. However, the large size of codebook makes it difficult to directly search the optimal precoder and combiner in practice. In this paper, we consider a general setup which has no a priori information about the channel, and propose an iterative scheme to optimize the precoder and combiner jointly. The proposed scheme uses the warm start strategy to perform initialization. By treating each observation of spectrum efficiency as a random variable, the proposed scheme utilizes the alternate discrete stochastic optimization which uses probabilistic forecasting, to find the optimum with reduced computational complexity. Moreover, we prove the convergence of the dis- crete stochastic optimization in our scenario. Simulation results show that the proposed algorithm outperforms the conventional algorithm in terms of higher spectrum efficiency and lower complexity. I. INTRODUCTION Millimeter wave (mmWave) communications have attracted growing attention from both academia and industry due to its abundant frequency spectrum [1]. However, it faces the critical challenge of large propagation loss caused by extreme- ly high frequency. A promising solution to compensate the severe attenuation is to use multiple-antenna beamforming [2]. Meanwhile, the short wavelength of mmWave makes it easy to integrate massive antenna elements. In order to maximize the flexibility, the beamforming is typically implemented in the digital domain, namely, digital beamforming, which in general needs to connect every antenna to a particular radio-frequency (RF) chain. As a result, the hardware cost increases significantly as the number of transmit antennas increases. In contrast, analog beamforming adopts phase shifter, which greatly reduces the hardware complexity and power consumption [3]. The analog beamforming algo- rithm proposed in [4] needs accurate channel state information (CSI), which is difficult to obtain in practice. To avoid complex estimation of CSI, the codebook-based beamforming is a promising technique, for which the op- timal precoding and combining matrices are chosen from the predefined codebook, without using the priori channel information. The intuitive and simplest scheme is exhaustive search. Unfortunately, the computation of exhaustive search Manuscript received August 8, 2016; revised September 9, 2016. This work was supported in part by the National Natural Science Foundation of China (Grant No. 61571082, 61371103 and 61601100). will become prohibitively complex, as the size of codebook increases. Various algorithms have been proposed to reduce the search complexity, among which the bidirectional training usually increases the protocol overheads [5]. The Tabu-TS search algorithm is proposed in [6], which can reduce search complexity obviously. However, it needs to restart repeatedly, and its random initialization cannot ensure the convergence to the global optimum. In this paper, we consider a practical scenario in which only the observations of spectrum efficiency can be obtained with random error, without knowing the CSI. In particular, we use the warm start strategy to perform initialization, which can avoid a large number of random tests to save searching overhead. After obtaining a relatively good initial value, we perform alternative optimization over the precoder and combiner, and the discrete stochastic optimization is used to optimize the precoder and combiner, respectively. We prove the convergence of discrete stochastic optimization algorithm in our proposed algorithm. The proposed method is also applicable to the time varying scenarios due to updated observations timely. Simulation results show that the proposed algorithm can achieve almost the same spectrum efficiency as the exhaustive search, and it reduces the search complexity significantly. The rest of this paper is organized as follows. Section II gives the mmWave MIMO system model. Section III presents the proposed algorithm and the convergence testimony. Section IV gives the simulation results. Finally, Section V concludes this paper. T , (·) The following notations will be used in this paper: Lower- case and upper-case boldface symbols represent vectors and matrices, respectively; (·) −1 , det (·) , E [·] denote transpose, conjugate transpose, inversion, determinant and expectation, respectively. diag (λ) is a matrix with the elements λ on its diagonal. In is a n-order identity matrix. {en}1×m is a 1 × m row vector with the n-th element as one and all other elements as zero. H , (·) II. SYSTEM MODEL As shown in Fig.1, the mmWave analog beamforming system consists of a transmitter equipped with Nt transmit antennas and nRF transmit chains, as well as a receiver equipped with Nr antennas and nRF receiver chains. The transmitter simultaneously transmits Ns data streams to the receiver. r t 978-1-5090-2860-3/16/$31.00 ©2016 IEEE

RF Chain RF Chain Baseband Signal Processing RFn t F tN channel rN W RFn r Baseband Signal Processing RF Chain RF Chain Analog Precoder Analog Combiner Fig. 1. The block diagram of mmWave MIMO system with analog beamforming. Assuming uniform linear array (ULA) antennas and narrow- band block-fading channels, we adopt the typical geometric Saleh-Valenzuela channel model [9] for the mmWave systems, i.e., the Nr × Nt channel matrix H is given by [10] H = NtNr L L l=1 αlar (θr l ) aH t θt l , (1) , θt where L is total number of scatter paths, αl is the complex gain of the l-th path. The θr l are the azimuth angles of l arrival (AOA) and the azimuth angles of departure (AOD), respectively. The column vectors ar (θr l ) denote the normalized receive and transmit antenna response at azimuth angle of θr l and θt l , respectively, which is given by [8] 1, eκd sin(θt l ),···, e κd(Nt−1) sin(θt l ) l ) and at (θt (2) θt l at = T T , 1, eκd sin(θr l ),···, e κd(Nr−1) sin(θr l ) ar (θr l ) = , (3) 1√ Nt 1√ Nr where κ = 2π λ and λ is the wavelength, d represents the antenna inter-element spacing. Denote the Ns × 1 symbol vector by s, which satisfies ssH analog precoder E matrix by F, each element of which satisfies |Fi,j|2 Nt . As a result, the transmitted signals is given by INs. Denote the Nt × nRF = 1 Ns = 1 t x = Fs. (4) Then the received signal y can be represented as √ ρHFs + n, y = (5) where ρ represents the transmit power, and n is an Nr × 1 noise vector all elements of which follow independent complex Gaussian distribution with zero mean and variance σ2. to receive data streams, and the combiner satisfies |Wi,j|2 ∼ y is written as Nr . After combination, the nRF analog combiner W is applied = r × 1 signal At the receiver, an Nr×nRF 1 r ∼ y = √ ρWH HFs + WH n. (6) In order to achieve high-rate transmission in MIMO sys- tems, we maximize the following spectrum efficiency by optimizing over the precoder F and the combiner W INs + n WH HFFH HHW R−1 ρ det σ2Ns R = log2 , (7) where Rn = WHW denotes covariance matrix of Gaussian noises after analog combining. So, the objective function is defined as R = Φ (F, W). The beam steering codebook have been proved to achieve the optimal capacity, i.e., under the limitation on the number of antennas, the array response vectors at (θt l ) are the optimal precoding vectors and the combining vectors in mmWave channels, respectively [7]. That is, the precoder and combiner are represented as follows l ) and ar (θr F = at ϕt 1 , at ϕt 2 ϕt nRF t , (8) ,···, at 2) ,···, ar W = ar (ϕr 1) , ar (ϕr ϕr nRF r , (9) i and ϕr where ϕt RF beam and receive RF beam, respectively. i denote the attitude angles for the i-th transmit We use Bt and Br to denote the bit number for quantizing the transmit attitude angles and the receive attitude angles, the possible values of ϕt are 2πn 2Bt , respectively. Then all codebook, whose cardinality is |F| = 2Bt × ×···× for n = 1, 2,···, 2Bt. We use F to denote the precoder 2Bt − nRF . It is noted that to achieve spatial diversity, t + 1 (for i = j) should be satisfied. = ϕt the condition ϕt i Similarly, the receive attitude angles are ϕr = 2πn 2Br , for n = × ··· × W is |W| = 2Br × 1, 2,···, 2Br. And the cardinality of the combiner codebook 2Br − nRF 2Br − 1 2Bt − 1 r + 1 . j III. OPTIMAL SOLUTION In this section, we propose an algorithm to maximize the spectrum efficiency R in (7), by optimizing the precoder matrix F and the combiner matrix W. 

A. Proposed Algorithm From [11], when the information of the solution of the orig- inal problem is properly used, the computational complexity for solving another closely related optimization problem can be reduced. The warm-start strategy is referred to obtain a good starting point for solving a nearby optimization problem [12]. In this paper, we use the mutual-information function as the objective function of the nearby optimization criterion, which is given by I = log2 det INr + HFFH HH . (10) ρ σ2Ns Then, the solution of optimizing the mutual information is used as the initial value of the precoder. That is equivalent to the case that the receiver uses the identity matrix as the combining matrix to receive the training sequence. Moreover, we utilize the discrete stochastic optimization algorithm to search the precoding and combining matrix in the process of alternate iteration [14]. The proposed algorithm is given as in the following Al- gorithm 1. First, the transmitter applies the initial precoder F0, which is chosen through the warm start strategy, to transmit training sequence. By using the discrete stochastic optimization, the receiver obtains the optimal combiner W1 opt. Alternatively, the receiver then fixes the combiner W1 opt, and the transmitter obtains the optimal precoder F1 opt by using discrete stochastic optimization. By repeating this iteration for M times, the final outputs FM opt converge to the optimum, which will be shown in Section IV. opt and WM Algorithm 1 Proposed Algorithm Step.1 Initialization by Using Warm Start Obtain the initial value of precoder F0. Step.2 Alternate Search for i = 1, 2,···, M opt , find the optimal Wi opt via discrete Fix Fi−1 stochastic optimization. Fix Wi stochastic optimization. end for opt, find the optimal Fi opt via discrete B. Discrete Stochastic Optimization Most of the proposed methods to solve (7) are based on the assumption that perfect CSI is known by the transmitter or the receiver. In contrast, without this assumption, we consider the scenario in which the objective function (7) cannot be evaluated analytically but be measured. We treat each observation of the spectrum efficiency as a random variable, which obeys the same type of distribution with the mean and the variance changing with different precoders and combiners. Thus, codebook searching problem becomes a discrete stochastic optimization problem [16]. An algorithm for solving discrete stochastic optimization problem updates its element from previous values towards a better values in each iteration. The element with maximum state occupation probability converges almost surely to the global optimizer. Thus the method spends most of the computational effort in the global optimizer rather than local optimal value [17]. Algorithm 2 Discrete Stochastic Optimization ♦ Initialization Randomly generate a starting point W0 ∈ W Set Ω = 0 , Wi ∈ W\W0 = 1 ; Ω 0, W0 0, Wi for k = 0, 1, 2,···, K ♦ Sampling and observation select another Wnew ∈ W\Wk uniformly. Obtain a observation Φ (F, Wnew). ♦ Acceptance if Φ (F, Wnew) > Φ Wk+1 = Wnew F, Wk else end if Wk+1 = Wk ♦ Update state occupation probabilities Ω [k + 1] = Ω [k] +ξ [k + 1] (q [k] − Ω [k]) with the normalizing factor ξ [k] = 1 k . ♦ Comparison and record the maximum ∧ Wk k + 1, Wk+1 k + 1, > Ω if Ω ∧ Wk+1 = Wk+1 else ∧ ∧ Wk Wk+1 = end if end for i The following Algorithm 2 is proposed for optimizing the combiner matrix W with given precoder matrix F0, via discrete stochastic optimization. We introduce the notations ∧ Wn represents the most frequently occupied s- first. The tate until the i-th iteration. The vector Ω denotes the state occupation probabilities with elements Ω [n, i] ∈ [0, 1] and Ω [n, i] = 1. The q [k] is an auxiliary vector for updating probability, i.e., q [k] ={e m}1×W, ifW m ∈ W has been selected in the k-th iteration. The ξ [k] is a normalizing factor to ensure the constraint of probability vector Ω. In particular, Algorithm 2 is described as follows. Firstly, the algorithm selects a starting combiner W0 ∈ W randomly and ∧ W0 = W0. Secondly, it selects another initializes Ω, where combiner randomly from codebook besides the current one, and obtains an independent observation. The probability of 1|W|−1 . Thirdly, it accepts a candidate Wnew is thus chosen as which has the larger value of spectrum efficiency for the next iteration. Fourthly, the algorithm updates the state occupation probability vector with ξ. Finally, the algorithm chooses the one that has the maximum of occupation probability, which 

almost surely converges to the global optimum [18]. When the number of iterations reaches the pre-defined maximum K, the algorithm will be terminated. It is noted that similar algorithm can be used to obtain the optimal precoder matrix F with given combiner matrix W in each iteration. Remark: Clearly, it is not necessary to store the sequences {Wn}, { ∧ W} and {Ωn} in Algorithm 2. In each iteration, they can be rewritten, since the earlier values will not be reused by the algorithm. C. Convergence testimony For the convergence of Algorithm 2, we have the following theorem. Theorem 1. The output of Algorithm 2 converges almost surely to the global maximum. an equivalent Proof: We define channel G as G (F, W) =F H HW, which incorporates the precoder ma- trix and the combiner matrix into the wireless channel matrix. Then the objective function (7) can be rewritten as Φ (F, W) = log2 det ρ σ2Ns R−1 n GGH . (11) INs + Let Sopt denote the state which achieves the global maxi- mum of the objection function, i.e., Sopt is equivalent to the optimal precoder Fopt and combiner Wopt . There always exist two arbitrary states Sm, Sn, such that Sm = Sopt,Sn = Sopt, and Sm = Sn. Assuming that the channels follow the Gaussian distribu- tion, the observation of spectrum efficiency in (7) also follows Gaussian distribution [19]. With different precoders and com- biners, the function has divergent means and variances. The observation in (7) has a positive bias, and it also has this fact, i.e., if Φ(Fi, Wi) > Φ(Fk, Wk), then μi > μk. Thus, the following two conditions hold Pr{Φ[Sopt] > Φ[Sm]} > Pr{Φ[Sm] > Φ[Sopt]} , Pr{Φ[Sopt] > Φ[Sn]} > Pr{Φ[Sm] > Φ[Sn]} . (12) (13) From [16], the Algorithm 2 will converge almost surely to the global maximum. This completes the proof. In the following, we explain the convergence intuitively. For the case of optimal combiner based on a certain precoder, the sequence { ∧ W} generated by Algorithm 1 is a Markov chain with state space W. Assuming that all the observations are independent, the elements of the transition probability matrix P (i, j) are given by P (i, j) = Pr ∧ Wk+1 = Wj| ∧ Wk = Wi (14) = 1|W|−1 Pr{Φ [F, Wj] > Φ [F, Wi]}, for all i, j ∈ W, i = j and ∧ Wk+1 = Wi| ∧ P (i, j) Pr{Φ [F, Wj] ≤ Φ [F, Wi]}, P (i, i) = Pr = 1 − j∈W\i j∈W\i Wk = Wi = 1|W|−1 TABLE I SIMULATION PARAMETERS Number of scatter paths Number of data streams The complex gain of path Array antenna type Number of antennas Number of iterations in Algorithm 1 maximum iteration of Algorithm 2 L = 3 Ns=2 αl ∼ CN (0, 1) ULA with d = λ 2 Nt=80, Nr=20 M =2 K = 400 when Bt = Br = 4; K = 800 when Bt = Br = 5; K = 2000 when Bt = Br = 6; for all i ∈ W. The process of searching precoder with given combiner can be derived in a similar way. When the objective function satisfies the conditions (12), we have P (j, i) > P (i, j) (Wi ∈ Sopt, Wj /∈ Sopt) . That means that the sequence { ∧ W} has a larger probability to transfer from an arbitrary state to the optimal state. The condition (13) states that P (j, i) > P (j, l) (Wi ∈ Sopt and Wj, Wl /∈ Sopt), i.e., an arbitrary state is more probable to move into the optimal state than into any other state. Thus the sequence { ∧ W} converges to the global maximum almost surely. IV. SIMULATION RESULTS We take the spectrum efficiency as the performance metric. The parameters of simulation are given in TABLE I. For convenience, we consider the case of Ns= nRF . SNR is defined as ρ σ2 . We assume that only 5 bits are used to quantize sin (θ) in [0, 1]. We take the Turbo-TS beamforming scheme [6] as performance benchmark. All the results are based on 105 Monto Carlo simulations for the realizations of random channels. t = nRF r Fig. 3 compares the spectrum efficiency for different sizes of codebook. It is observed that the proposed algorithm achieves almost the same spectrum efficiency achieved by the exhausted search, which is higher than that of the Turbo-TS scheme. Fig. 4 compares the complexity for different schemes. The number of calculation in the objective function is defined as algorithm complexity. The complexity of Turbo-TS scheme is calculated based on the data given in [6]. It is observed that the proposed algorithm decreases the complexity significantly, compared to the exhausted search and the Tabu-TS scheme. Fig. 5 compares the spectrum efficiency under the same complexity. Compared to the Turbo-TS algorithm , the spec- trum efficiency of the proposed algorithm increases by 10%. As the number of quantization bits increases, the proposed algorithm achieves more improvement of spectrum efficiency performance than the Turbo-TS scheme. V. CONCLUSION (15) In this paper, we have studied the codebook-based beam- forming for millimeter-wave system. We consider a general setup which has no CSI, and propose an iterative scheme to optimize the precoder and combiner jointly. The warm start strategy is used to perform initialization. By treating each observation of the spectrum efficiency as a random 

Exhaustive search Bt=Br=6 Proposed search Bt=Br=6 Tabu-TS search Bt=Br=6 Exhaustive search Bt=Br=5 Proposed search Bt=Br=5 Tabu-TS search Bt=Br=5 Exhaustive search Bt=Br=4 Proposed search Bt=Br=4 Tabu-TS search Bt=Br=4 12 10 8 6 4 2 ) z H / s p b ( y c n e i c i f f e m u r t c e p S 0 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 SNR(dB) Fig. 2. Spectrum Efficiency comparison by various searching solutions. Proposed search Tabu-TS search Exhaustive search y t i x e l p m o c 8 10 7 10 6 10 5 10 4 10 3 10 2 10 Ns=1 5bit Ns=1 6bit Ns=1 7bit Ns=2 4bit Ns=2 5bit Ns=2 6bit Fig. 3. Algorithm complexity comparison by various searching solutions with different size of codebook. Proposed search Bt=Br=6 Tabu-TS search Bt=Br=6 Proposed search Bt=Br=5 Tabu-TS search Bt=Br=5 Proposed search Bt=Br=4 Tabu-TS search Bt=Br=4 12 10 8 6 4 2 ) z H / s p b ( y c n e i c i f f e m u r t c e p S 0 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 SNR(dB) Fig. 4. Achieved performance comparison under the same complexity. variable, the proposed scheme utilizes the alternate discrete stochastic optimization to find the optimum and reduce the complexity. Moreover, the convergence of the discrete stochas- tic optimization is proved. Simulation results verify that the proposed algorithm achieves higher spectrum efficiency and lower complexity. For the future work, we will focus on tracking time-varying scenarios and propose adaptive schemes. REFERENCES [1] Su .Yong and C. Chong, “An Overview of Multigigabit Wireless through Millimeter Wave Technology: Potentials and Technical Chal- lenge,” EURASIP J. Wireless Commun. and Networking, vol. 2007, no. 1, pp. 1-10, Jun. 2006. [2] G. J. Foschini and M. J. Gans, “On the limits of wireless communica- tions in a fading environment when using multiple antennas,” Wireless Personal Commun., vol. 6, no. 3, pp. 311-335, 1998. [3] V. Venkateswaran and A. J. van der Veen, “Analog Beamforming in MIMO Communications With Phase Shift Networks and Online Channel Estimation,” IEEE Trans. Signal Process., vol. 58, no. 8, pp. 4131-4143, Aug. 2010. [4] E. Zhang and C. Huang,“On achieving optimal rate of digital precoder by RF-baseband codesign for MIMO systems,” IEEE Veh. Technol. Conf.(VTC14 Fall), pp. 1-5. Sep. 2014, [5] S. Hur, T. Kim, D. Love, J. Krogmeier, T. Thomas, and A. Ghosh, “Millimeter wave beamforming for wireless backhaul and access in small cell networks,” IEEE Trans. Commun., vol. 61, no. 10, pp. 4391-4403, Oct. 2013. [6] X. Gao and L. Dai and C. Yuen and Z. Wang, “Turbo-Like Beamforming Based on Tabu Search Algorithm for Millimeter-Wave Massive MIMO Systems,” IEEE Trans. Veh. Technol., vol. 65, no. 7, pp. 5731-5737, Jul. 2016. [7] O. E. Ayach and R. W. Heath and S. Abu-Surra and S. Rajagopal and Z. Pi,“The capacity optimality of beam steering in large millmeter wave MIMO systems”, IEEE 13th Int. Workshop on Signal Processing Advances in Wireless Commun. (SPAWC), pp. 100-104, Jun. 2012. [8] C. Balanis, Antenna theory. Wiley New York, 1997. [9] A. A. M. Saleh and R. Valenzuela,“A Statistical Model for Indoor Multipath Propagation,” IEEE J. Sel. Areas Commun., vol. 5, no. 2, pp. 128-137, Feb. 1987. [10] O. E. Ayach, S. Rajagopal, S. Abu-Surra, Z. Pi and R. W. Heath, “Spatially Sparse Precoding in Millimeter Wave MIMO Systems,” IEEE Trans. Wireless Commun., vol. 13, no. 3, pp. 1499-1513, Mar. 2014. [11] E. Yildirim and S. wright ,“Warm-Start strategies in interior methods for linear programming”, Society for Industrial and Applied Mathematics, vol. 12, no. 3, pp. 782-810, 2002. [12] E. John E.Yildirim ,“Implementation of warm-start strategies in interior- point methods for linear programming in fixed dimension”, Computation- al Optimization and Applications, vol. 41, no. 2, pp. 151-183. Nov. 2008. [13] Kang, M. and Alouini, M.S.,”Capacity of MIMO Rician Channels ”, IEEE Trans. Wireless Commun., vol.5, no. 1, pp. 112-122. Jan. 2006. [14] C. Qi and L. Wu, “Optimized Pilot Placement for Sparse Channel Estimation in OFDM Systems,” IEEE Signal Process. Lett., vol. 18, no. 12, pp. 749-752, Dec. 2011. [15] I. Berenguer, Xiaodong Wang and V. Krishnamurthy, “Adaptive MIMO antenna selection via discrete stochastic optimization,” IEEE Trans. Signal Process., vol. 53, no. 11, pp. 4315-4329, Nov. 2005. [16] S. Andradottir, “A global search method for discrete stochastic optimiza- tion,,” SIAM J. Optimiz.,vol. 6, no. 2, pp. 513-530, May 1996. [17] S. Andradottir,“Accelerating the Convergence of Random Search Meth- ods for Discrete Stochastic Optimization”, ACM Transactions on Model- ing and Computer Simulation, vol. 9, no. 4, pp. 349-380, Oct 1999. [18] R. Regis,“Convergence guarantees for generalized adaptive stochastic search methods for continuous global optimization”, European Journal of Operational Research, vol. 207, no. 3, pp. 1187-1202, Dec. 2010. [19] A. Goldsmith, S. A. Jafar, N. Jindal and S. Vishwanath, “Capacity limits of MIMO channels,” IEEE J. Sel. Areas Commun., vol. 21, no. 5, pp. 684-702, Jun. 2003.