Theoretical Investigation of Convergence of Max-SINR Algorithm in the MIMO Interference Network

Show more

1. Introduction

To date, different approaches have been developed to address interference management. Beside the conventional methods for interference management [1] , a new method termed “interference alignment” (IA) has been proposed by the researchers. The basic idea behind the IA is to fit undesirable signals into a small portion of the signal space, observed by each receiver (interference subspace), and then leave the remaining signal space free of any interference for the desired signal (signal subspace). In [1] - [12] , and [13] , the authors implement the IA for different scenarios.

Transceiver for multi-input multi-output (MIMO) interference channel (IC) has been designed by progressive minimization of the leakage interference, Algorithm 1 in [4] . In this scheme, the IA is achieved only at very high SNRs. The Max-SINR algorithm, Algorithm 2 in [4] , is another approach to obtain IA. This technique shows significant improvements in terms of sum rate in the range of low-to-intermediate SNRs and achieves the IA at high SNR.

The algorithm 1 seeks perfect interference alignment. In particular, it seeks to create an interference-free subspace of the required number of dimensions that is designated as the desired signal subspace. However, Algorithm 1 makes no attempt to maximize the desired signal power within the desired signal subspace. In fact, Algorithm 1 does not depend at all on the direct channels through which the desired signal arrives at the intended receiver. Therefore, while the interference is eliminated within the desired space, no coherent combining gain (array gain) for the desired signal is obtained with Algorithm 1. While this is optimal as all signal powers approach infinity, it is not optimal in general at intermediate SNR values. Therefore, Algorithm 2 may be designed which will perform better than Algorithm 1 at intermediate SNR values.

Authors show that Algorithm 1 converges and convergence of Max-SINR is not presented. Since all the iterative algorithms have meaning when converges. No convergence proof has been presented in literature for Max SINR algorithm. In this paper, convergence issue of Max-SINR is investigated. It is shown how the Max-SINR algorithm proposed by Gomadam et al. converges by considering an equivalent problem, i.e. a constrained maximization problem.

Convergence of robust MMSE is shown in [14] theoretically. Total fraction of interference leakage to received signal parameter is used to show convergence numerically. To validate the correctness of the proposed proof, numerical convergence behavior of the Max SINR is compared with robust MMSE.

2. System Model

In a K-user MIMO IC, transmitter j and receiver k have M and N antennas, respectively. Independent symbols
${D}^{j}$ with power P are sent by the j^{th} transmitter. Channel matrices between transmitter j and receiver k is denoted by
${H}^{kj}$ . The received signal at receiver k is expressed by

${Y}^{k}=\underset{j=1}{\overset{K}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{H}^{kj}{X}^{j}+{Z}^{k}$ (1)

where ${X}^{j}$ is the $M\times 1$ signal vector transmitted by the transmitter j and ${Z}^{k}~CN\left(0,{N}_{0}I\right)$ is additive white Gaussian noise (AWGN) vector. Beam-forming strategy is used based on the interference alignment. In particular, transmitter j precodes symbol vector by using the precoder matrix. ${V}^{j}$ is the $M\times {D}^{j}$ precoder matrix. Columns of ${V}^{j}$ , ${v}_{d}^{j}$ , are unit norm vectors. Receiver k estimates the transmitted symbol vector ${s}^{k}$ by using the interference suppression matrix ${U}^{k}$ . The received signal is filtered by ${U}^{k}$ as $\stackrel{\xaf}{{Y}^{k}}={U}^{k}{}^{\u2020}{Y}^{k}$ .

Each node works in a time division duplex (TDD) mode. At two consecutive time slots, first, nodes on the left-hand side send the data to the nodes on the right-hand side. Then the role of nodes is switched and the nodes on the left-hand side receive the data, as illustrated in Figure 1.

The relation between the original and reciprocal channel matrices is $\stackrel{\leftarrow}{{H}^{jk}}={H}^{kj}{}^{\u2020}$ [4] . Since the receivers of the reciprocal channel play the roles of

Figure 1. System model.

original network’s transmitters and vice versa, then $\stackrel{\leftarrow}{{V}^{k}}={U}^{k}$ and $\stackrel{\leftarrow}{{U}^{j}}={V}^{j}$ .

According to the system model, the SINR value for the d^{th} data stream at k^{th} receiver is expressed by (where,
$\Vert \text{\hspace{0.05em}}.\text{\hspace{0.05em}}\Vert $ denotes the Euclidian norm.)

$SIN{R}_{d}^{k}=\frac{P{\Vert {u}_{d}^{k}{}^{{}^{\u2020}}{H}^{kk}{v}_{d}^{k}\Vert}^{2}}{P{\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{m=1}^{{D}^{j}}{\Vert {u}_{d}^{k}{}^{{}^{\u2020}}{H}^{kj}{v}_{m}^{j}\Vert}^{2}}}-P{\Vert {u}_{d}^{k}{}^{{}^{\u2020}}{H}^{kk}{v}_{d}^{k}\Vert}^{2}+{N}_{0}{\Vert {u}_{d}^{k}\Vert}^{2}}$ (2)

Alternatively $SIN{R}_{d}^{k}$ can be expressed by

$SIN{R}_{d}^{k}=\frac{{u}_{d}^{k}{}^{\u2020}{T}_{d}^{k}{u}_{d}^{k}}{{u}_{d}^{k}{}^{\u2020}\left[{S}^{k}-{T}_{d}^{k}+{N}_{0}I\right]{u}_{d}^{k}}$ (3)

where
${S}^{k}=P{\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{m=1}^{{D}^{j}}{H}^{kj}{v}_{m}^{j}{v}_{m}^{j}{}^{{}^{\u2020}}{H}^{kj}{}^{{}^{\u2020}}}}$ and
${T}_{d}^{k}=P{H}^{kk}{v}_{d}^{k}{v}_{d}^{k}{}^{{}^{\u2020}}{H}^{kk}{}^{{}^{\u2020}}$ denote, respectively, the covariance matrix of all data streams observed by the receiver k and covariance matrix of the d^{th} desirable data stream.

3. Proof of Convergence of Max-SINR Algorithm

Max-SINR algorithm is presented in algorithm 2 in [4] . It is repeated in Table 1.

Maximizing (3) over ${u}_{d}^{k}$ can be written as follow

$\mathrm{max}\frac{{u}_{d}^{k}{}^{{}^{\u2020}}G{u}_{d}^{k}}{{u}_{d}^{k}{}^{{}^{\u2020}}F{u}_{d}^{k}}$ (4)

where matrices are $G={G}^{\u2020}={T}_{d}^{k}\ge 0$ , and $F={F}^{\u2020}={S}^{k}-{T}_{d}^{k}+{N}_{0}I>0$ . It is shown in [15] that the optimization problem in (4) is equivalent to

$\begin{array}{l}\mathrm{max}{u}_{d}^{k}{}^{{}^{\u2020}}G{u}_{d}^{k},\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}{u}_{d}^{k}{}^{{}^{\u2020}}F{u}_{d}^{k}=1.\end{array}$ (5)

For the equivalent problem, i.e. constrained maximization in (5), Lagrangian function is $l\left({u}_{d}^{k},\lambda \right)={u}_{d}^{k}{}^{{}^{\u2020}}G{u}_{d}^{k}+\lambda \left(1-{u}_{d}^{k}{}^{{}^{\u2020}}F{u}_{d}^{k}\right)$ . Lagrange conditions are

Table 1. Max SINR algorithm.

$\frac{\partial l\left({u}_{d}^{k},\lambda \right)}{\partial {u}_{d}^{k}}=0$ and $\frac{\partial l\left({u}_{d}^{k},\lambda \right)}{\partial \lambda}=0$ . The solution is denoted by ${u}_{d}^{k}{}^{*}$ and Lagrange

multiplier by ${\lambda}^{*}$ . It is also shown in [15] that ${u}_{d}^{k}{}^{*}$ is the eigenvector corresponding to the maximal eigenvalue of ${F}^{-1}G$ and ${\lambda}^{*}$ is ${u}_{d}^{k}{{}^{*}}^{{}^{\u2020}}G{u}_{d}^{k}{}^{*}$ .

Therefore, the unit vector that maximizes (3), is given by

${u}_{d}^{k}=\vartheta \left[{F}^{-1}G\right]$ (6)

where operator $\vartheta [.]$ denotes the eigenvector corresponding to the maximal eigenvalue of a matrix.

The convergence of the algorithm is proved by considering total Lagrangian function of all data streams in the network $\sum}_{k=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}l\left({u}_{d}^{k},\lambda \right)$ . The metric is defined in (7). The function is unchanged in the original and reciprocal networks since the transmit and receive ﬁlters change their roles. Therefore, each step [4, Algorithm 2] in the algorithm increases the value of the function. This implies that the algorithm converges.

${\mathrm{max}}_{\begin{array}{l}\text{\hspace{0.17em}}{V}^{j}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{U}^{K}\\ \forall j\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}k\in \mathcal{K}\end{array}}metric={\displaystyle {\sum}_{k=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}l\left({u}_{d}^{k},\lambda \right)}}$ (7)

Accordingly:

${\mathrm{max}}_{\begin{array}{l}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{U}^{K}\\ \forall k\in \mathcal{K}\end{array}}metric={\displaystyle {\sum}_{k=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}{\mathrm{max}}_{{u}_{d}^{k}}l\left({u}_{d}^{k},\lambda \right)}}$ (8)

In other words, given ${V}^{j}\text{\hspace{0.17em}}\forall j\in \mathcal{K}$ , Step 4 [4, Algorithm 2] increases the value of (7) over all possible choices of ${U}^{k}\text{\hspace{0.17em}}\forall k\in \mathcal{K}$ . The filter $\stackrel{\leftarrow}{{U}^{j}}$ computed in Step 7 [4, Algorithm 2], based on $\stackrel{\leftarrow}{{V}^{k}}={U}^{k}$ , also maximizes the metric in the reciprocal channel (9).

${\mathrm{max}}_{\begin{array}{l}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\stackrel{\leftarrow}{{U}^{j}}\\ \forall j\in \mathcal{K}\end{array}}\stackrel{\leftarrow}{metric}={\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}\stackrel{\leftarrow}{l}\left(\stackrel{\leftarrow}{{u}_{d}^{j}},\stackrel{\leftarrow}{\lambda}\right)}}={\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}{\stackrel{\leftarrow}{{u}_{d}^{j}}}^{\u2020}\stackrel{\leftarrow}{G}\stackrel{\leftarrow}{{u}_{d}^{j}}+\stackrel{\leftarrow}{\lambda}\left(1-{\stackrel{\leftarrow}{{u}_{d}^{j}}}^{\u2020}\stackrel{\leftarrow}{F}\stackrel{\leftarrow}{{u}_{d}^{j}}\right)}}$ (9)

Since $\stackrel{\leftarrow}{{V}^{k}}={U}^{k}$ and $\stackrel{\leftarrow}{{U}^{j}}={V}^{j}$ , the metric remains unchanged in the original and reciprocal networks, according to following equation:

$\begin{array}{l}\stackrel{\leftarrow}{metric}={\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}{u}_{d}^{j}{}^{{}^{\u2020}}{T}_{d}^{j}{u}_{d}^{j}}}+{\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}{\lambda}_{d}^{j}\left(1+{u}_{d}^{j}{}^{{}^{\u2020}}\left[{T}_{d}^{j}-{N}_{0}I\right]{u}_{d}^{j}\right)}}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.05em}}-P{\displaystyle {\sum}_{j=1}^{K}{\displaystyle {\sum}_{d=1}^{{D}^{j}}{\displaystyle {\sum}_{k=1}^{K}{\displaystyle {\sum}_{m=1}^{{D}^{j}}{\lambda}_{d}^{j}{u}_{m}^{k}{}^{{}^{\u2020}}{H}^{kj}{v}_{d}^{j}{v}_{d}^{j}{}^{{}^{\u2020}}{H}^{kj}{}^{{}^{\u2020}}{u}_{m}^{k}}}}}=metric\end{array}$ (10)

Therefore, Step 7 [4, Algorithm 2] also can increase the value of (7). Since the value of (7) is monotonically increased after every iteration, convergence of the algorithm is guaranteed.

4. Simulation Results

Simulation results to validate the correctness of the proposed proof are based on fraction of interference leakage to the received signal parameter [14] . Figure 2 and Figure 3 show total fraction of interference leakage to received signal. Since convergence of robust MMSE is shown in [14] , its total parameter is plotted in Figure 2 and Figure 3 as well. Convergence behavior of the algorithm in comparison with robust MMSE implies a convergent scheme.

Figure 2. Sum of fraction of interference leakage to received signal at each user. $M=N=3$ , $D=1$ , $K=4$ interference network with ${\sigma}^{2}=0.1$ , and $\frac{P}{{N}_{0}}=10\text{\hspace{0.17em}}\text{dB}$ .

Figure 3. Sum of fraction of interference leakage to received signal at each user. $M=3$ , $N=4$ , $D=2$ , $K=2$ interference network with ${\sigma}^{2}=0.1$ , and $\frac{P}{{N}_{0}}=10\text{\hspace{0.17em}}\text{dB}$ .

References

[1] Jafar, S. and Fakhereddin, M. (2007) Degrees of Freedom for the MIMO Interference Channel. IEEE Transactions on Information Theory, 53, 2637-2642.

https://doi.org/10.1109/TIT.2007.899557

[2] Gou, T. and Jafar, S.A. (2010) Degrees of Freedom of the K User M × N MIMO Interference Channel. IEEE Transactions on Information Theory, 56, 6040-6057.

https://doi.org/10.1109/TIT.2010.2080830

[3] Cadambe, V. and Jafar, S.A. (2008) Interference Alignment and the Degrees of Freedom of the K User Interference Channel. IEEE Transactions on Information Theory, 54, 3425-3441.

https://doi.org/10.1109/TIT.2008.926344

[4] Gomadam, K., Cadambe, V.R. and Jafar, S.A. (2011) A Distributed Numerical Approach to Interference Alignment and Applications to Wireless Interference Networks. IEEE Transactions on Information Theory, 57, 3309-3322.

https://doi.org/10.1109/TIT.2011.2142270

[5] Zhu, B., Ge, J., Li, J. and Sun, C. (2012) Subspace Optimization-Based Iterative Interference Alignment Algorithm on the Grassmann Manifold. IET Communications, 6, 3084-3090.

https://doi.org/10.1049/iet-com.2012.0467

[6] Yu, H. and Sung, Y. (2010) Least Squares Approach to Joint Beam Design for Interference Alignment in Multiuser Multi-Input Multi-Output Interference Channels. IEEE Transactions on Signal Processing, 58, 4960-4966.

https://doi.org/10.1109/TSP.2010.2051155

[7] Papailiopoulos, D.S. and Dimakis, A.G. (2012) Interference Alignment as a Rank Constrained Rank Minimization. IEEE Transactions on Signal Processing, 60, 4278-4288.

https://doi.org/10.1109/TSP.2012.2197393

[8] Du, H., Ratnarajah, T., Sellathurai, M. and Papadias, C.B. (2013) Reweighted Nuclear Norm Approach for Interference Alignment. IEEE Transactions on Communications, 61, 3754-3765.

https://doi.org/10.1109/TCOMM.2013.071813.130065

[9] Kumar, K.R. and Xue, F. (2010) An Iterative Algorithm for Joint Signal and Interference Alignment. 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), 13-18 June 2010, Austin, TX, 2293-2297.

https://doi.org/10.1109/ISIT.2010.5513646

[10] Schmidt, D.A., Shi, C., Berry, R.A., Honig, M.L. and Utschick, W. (2009) Minimum Mean Squared Error Interference Alignment. 2009 Conference Record of the 43 Asilomar Conference on Signals, Systems and Computers, 1-4 November 2009, Pacific Grove, CA, 1106-1110.

https://doi.org/10.1109/ACSSC.2009.5470055

[11] Santamaria, I., Gonzalez, O., Heath, R.W. and Peters, S.W. (2010) Maximum Sum-Rate Interference Alignment Algorithms for MIMO Channels. 2010 IEEE Global Telecommunications Conference (GLOBECOM 2010), 6-10 December 2010, Miami, FL, 1-6.

https://doi.org/10.1109/GLOCOM.2010.5683919

[12] Gao, H., Leithon, J., Yuen, C. and Suraweera, H.A. (2013) New Uplink Opportunistic Interference Alignment: An Active Alignment Approach. 2013 IEEE Wireless Communications and Networking Conference (WCNC), 7-10 April 2013, Shanghai, 3099-3104.

https://doi.org/10.1109/WCNC.2013.6555057

[13] Peters, S.W. and Heath Jr., R.W. (2009) Interference Alignment via Alternating Minimization. 2009 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2009), 19-24 April 2009, Taipei, 2445-2448.

https://doi.org/10.1109/ICASSP.2009.4960116

[14] Shen, H., Li, B., Tao, M. and Luo, Y. (2010) The New Interference Alignment Scheme for the MIMO Interference Channel. 2010 IEEE Wireless Communications and Networking Conference (WCNC), 18-21 April 2010, Sydney.

https://doi.org/10.1109/WCNC.2010.5506770

[15] Chong, E.K.P. and Zak, S.H. (2001) An Introduction to Optimization. John Wiley & Sons, Hoboken, 382-383.