TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 13, No. 2, Februa ry 20 15, pp. 337 ~ 351   DOI: 10.115 9 1 /telkomni ka. v 13i2.700 3          337     Re cei v ed Se ptem ber 5, 2014; Re vi sed  No vem ber 9,  2014; Accept ed De cem b e r  6, 2014   A New Approa ch to Linear Estimation Problem in Multi- user Massive MIMO Systems      Muhammad  Ali Raza Anj u m  Arm y  Pub lic C o lle ge of Ma na geme n t and Sc ienc es, Ra w a lp indi, Pak i stan   E-mail: ali.raz a .anjum@ g ma il. com      A b st r a ct  A novel  appr o a ch for solvi n g  line a r esti mati on pro b l e m  in mu lti-user mas s ive MIMO systems i s   prop osed. In th is ap proac h, th e difficu lty of matrix inv e rsio n i s  attributed to t he i n co mp lete defin ition of  th e   dot pro duct. T he g ener al d e finitio n  of d o t product i m p lies  that the col u mns of  chan ne l matrix  are a l w a y s   orthog on al w h ereas, i n  pr actice, they  may  be n o t. If  the l a tter infor m ati on ca n b e  i n c o rpor ated  into  dot   prod uct, then  the unk now ns  can be  direct ly co mpute d   from  proj ectio n s  w i thout invert ing th e cha n n e l   matrix. By  doi ng so, th e pr o pose d   meth od  is ab le to  ach i eve  an  exact  soluti on w i th a  25% r e d u ctio n  i n   computati o n a l  compl e xity as  compar ed to t he QR  meth o d . Propos ed  meth od  is sta b le, offers a n   extra   flexibi lity of co mp utin g any si ngl e unk now n, and ca n be i m ple m ented i n  ju st tw elve lin es of code.     Ke y w ords :  est i matio n , large,  mass ive, MIMO, multi-user     Copy right  ©  2015 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Multiple Input Multiple Output (MIMO)  sy stem s in co rpo r ate m u ltiple ante nna s at the  transmitter a nd the  re ceiv er to  improve  the d a ta ra te  of wi rele ss  communi catio n  sy stem s [1,  2].    Ho wever, the  ever growi n g  desi r e for th e increa se d d a ta rate s can  hardly be  sat i ated and th e r e  is a  dem and   to increa se  th e data  rate s  even furth e r.  As a  re sult, t he resea r che r s  are aimi ng  to   achi eve the  asymptotic li mits in  cap a c ity. Rec ently, it has b een  demo n strate d that very h i gh  cap a citie s   are a c hievabl e  on fo rward  and  reve rs e  links a s  th e  numbe r  of transmit  anten nas  approa che s  i n finity [3]. Such  system s in whi c h a  relatively la rge n u mbe r   of base stati o n   antenn as  serve a large nu mber of u s ers are kn own as  Mas s i ve MI MO s y s t ems   (M-MIMO) [4].  M-MIMO  systems provide  variou s adv antage s  over the tradition al MIMO sy stem s.  These sy ste m s promi s e  highe r data rates, high er   antenn a re so lution, lowe r  error p r ob abil i ties,  lowe r therm a l  noise, an d lo wer tran smit power  pe r ant enna. The s e  advantag es  can be attribut ed   to an ove r all  averagi ng b e havior  of the s e  system s.  But these  ad vantage s be come eve n  m o re  impre s sive i n  the multi - use r   scena ri o wh ere  the  base  statio n tran smits  to seve ral u s ers   simultan eou sl y. Howeve r,  multi-u s er  M-MIMO  systems in cu r costs  of their own: in clud ing   increa se in   hard w a r e, in cre a se in  po wer con s um ption, and i n cre a se in  ph ysical  sp aci n g .   Eventually, th e transceive r   become s  co mplex as well  [3-6].   Tran sceiver  compl e xity is currently an  issu e of gre a t con c ern in  M-MIMO sy stem s. It  has be en  sh own  that fo r  the poi nt to  point   scen ario, the d e cod i ng  compl e xity of the  re cei v er  alone g r o w s  expone ntially with increa se in the  num ber of tra n smit antenna s [7]. In case  of a  multi-u s er  scenari o , the transmitte r be come s  com p l e x as  well b e ca use the t r an smitter n o w   requi re s adv anced codin g  scheme s  to manag e si multaneo us t r an smi ssi on  of informatio n to   multiple u s e r s. Fo rme r  op eration,  kn o w n a s   de cod i ng, and  the  latter on e,  calle d p r e c o d ing,  gene rally co mpri se the tra n sceiver o p e r ation [8].    For a larg e n u mbe r  of transmit anten n a s,  linea r de cod e rs and p r ecode rs have proven  almost  optim al [9-1 1]. Th ese  line a r  preco ders/ de co ders  req u ire   the inversio n  of a  potenti a lly  large  ch ann e l  matrix. For example, a  pra c tica l  preco d ing m e thod i s   the Z e ro -forcing  (ZF)  pre c odi ng m e thod  whi c h  comp utes the  pre c odi ng m a trix by formi ng the p s e u d o inverse of t he  cha nnel  matri x  [9]. Similar to lin ear p r e c odi ng, a  si mple lin ea r d e co der i s  the  MMSE d e co der  whi c h  comp u t es the  de cod i ng matrix by  again fo rm in g  the p s eud oin v erse  of the  cha nnel m a tri x   [12]. If the di mensi o n s  of  a sy stem a r e  very  la rge, i n verting th e  cha nnel  matrix become s   a  c u mbers o me tas k  [4].  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 13, No. 2, Februa ry 2015 :  337 – 351   338 Therefore, th ere is a ne e d  to eliminate  the outrigh t inversion.  Variou s meth ods for  approximate matrix  inversion  have  be en propo se d  in literatu r e :  includi ng  Cayley-Hamil ton   theore m   met hod, Neum a nn seri es  ex pan sion me t hod,  Q R  de comp ositio n method, ran dom  matrix metho d s, and met hod s ba sed  on polynom i a l and trun cat ed polynomi a l filters [13-2 1 ].  These metho d s  still requi re a lot of co mputational   e ffort and som e  of them ha ve proven to  be  even mo re  co mplex than  th e direct i n version.  Ho we ve r, it is impo rta n t to note  tha t  the challe ng e   is fun dam ent ally different  i n  at le ast  thre e po ss ible  wa ys. To  begi n  with, the  cha nnel  matrix d oes  not have  a  st ructu r e. Se co ndly, inste ad  of bein g   dete r mini stic, it i s  ran dom. Fi n a lly, there i s   no  guarantee  of spa r sity. So we can di sp ense with  th e tradition al method s for  solving the li nea r  estimation p r oblem [22].   With this in view, we p r op ose a n o vel method to so lve such larg e linear  syste m s. Th e   prop osed m e thod tre a ts th e linea r e s tim a tion p r obl em  as  a  coo r din a te tran sfo r m a tion p r obl em.  By doing so, the method i s  able to a c h i eve zero no rms in erro r a nd re sidu e in  contra st to the   state of  the  a r t iterative  me thods for larg e sy stem s –   LSQR,  LSMR, and  Kaczm a rz that  achie v e   much  highe r  norm s  - a nd  a 25% red u cti on in co mput ation co mple xity when co mpared to th e QR  method, the  leadin g  prota goni st in exa c t met hod s [ 23-2 5 ]. Also  by employing  the pro p o s e d   method, a p a r ticula r u n kno w n, which ma y be the  only  informatio n re quire d by a  si ngle u s e r , ca n   be  comp uted  witho u t eval uating th e e n t ire  solution  v e ctor  while no such flexibil ity is availabl e in   the traditio nal  method s. Fu rtherm o re, th e metho d  is stable an d lig h t  on comput ation a s   well a s  it  only relie s on  multiplicatio n with sim p le  ran k -o ne p r o j ection mat r ices for o b taini ng the sol u tio n .  Finally, the method can be  prog ram m ed  in just ten line s  of cod e s.   Re st of the  a r ticle i s   org a n ize d  a s  follo ws . Se ction   2 begi ns with  a sy stem m odel a nd  define s  the  u nderlyin g p r o b lem.  Ba si c i dea  behi nd t he p r o posed   method  is ex plore d  in  Se ction   3. The metho d  is then explained in Sect ion 4. Se ction 5 contain s  its compl e te p r oof. Section  6  provide s  th e  proof  of the   choi ce  of  refl ection  matri c es. A  co mple te algo rithm f o r  step  by  step  solutio n  of the line a r  est i mation p r obl em a c cordi n g to the p r o posed meth o d  is o u tlined  in  Section  7. Th is  se ction  also in clud es a  use r-f ri endly  cod e  fo r the   algorith m . Co mpari s o n  of t h e   prop osed me thod with Q R  deco m po sition is carried  out in se ction  8. The pro c e ss of ge ne rati on  of inverse ve ctors i s  al so   discu s sed in   this  se ction.  Comp utation a l complexity of the p r o p o s ed  algorith m  is  analyzed in  Section 9  which i s  fo llo wed by its  sta b ility analysis in Section  10.  Section 11 co nclu de s the article in whi c h  the co mpa r ison of the pro posed metho d  is carrie d out  with the state  of the art methods avail abl e in literature for so lving la rge syste m s.       2. Problem  A narrowban d memo ryless MIMO  cha n nel with   tran smit and   re ceive antenn a s  can  be model ed a s  a syste m  of linear eq uati ons [13].          (1)   With,      ⋮    ⋮    ⋮     (2)  is a large, random and no n-spa r se matrix.   is the input vector.   is  the output vector. Zero   Forcing (ZF)  estimate   of the input vect or is:         (3) Re cov e ry  of    requi re s the i n versi on of a potentially large matrix   .    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A New App r o a ch to Lin ear  Estim a tion Problem  in Multi-user …  (Mu ham m ad Ali  Ra za Anjum )   339 3. Basic Idea   Linea r e s tim a tion proble m  pre s e n ted  by Equation  (3)  ca n be  viewed  as  a  coo r din a te  transfo rmatio n probl em.   can be e n visag ed as th e vector that  undergoe s the coo r di nat e   transfo rmatio n,   repre s ent s its coo r din a t es in the new coo r di nate system, and   contai ns  th e   basi s  vecto r s for the new coo r din a te sy stem [ 26]. The basi s  vecto r s can be o r thogo nal or n on- orthog onal.  For the first case, we are l ead to t he cla ssi c Le ast Sq uare s  (LS) so lution depi cte d  in   Figure 1.         Figure 1. Co mputation of unkno wn s  in an ortho gon al  coordinate  system       In this  c a s e , the es timates   , ,…,  are the proje c tion s of   on the re spe c tive  basi s  vectors.      ⋮   (4) Whe n  the basis vecto r s are not orthogo nal,   is computed by forming the inverse of    matrix. This i s  preci s ely what we de si re  to avoid. We would li ke to comp ute    from the direc t   estimate  of th e proje c tion s. In o r de r to  d o  so, we fo cu s o u r  attentio n on  Figu re  2  for th e  ca se  of  non-orth ogo n a l basi s  ve ctors. A s  ca n  be ob se rved  from figure, e m ploying the  definition of  do t  prod uct in Eq uation (4)  will  yield much l onge r  e s timates than th e a c tual on es.  Reason for th e s e  inco rrect e s ti mates  ca n b e  attribute d  to the p r e s en ce of id entity matrix in the  gene ral d e fini tion  of the dot pro duct. We d e m onst r ate thi s  fact by  re-writing the first  term in Equat ion (4 ).          Figure 2. Co mputation of first un kno w n i n  a non-orth o gonal  coo r din a te system   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 13, No. 2, Februa ry 2015 :  337 – 351   340         (5)   Identity matrix   depi cts a set of orthogo nal ba sis ve ctors. As they a r e not, we  ca n  repla c e the   matrix in Equation (5 ) by another m a trix, say  .        (6) To s o lve for  ,  we re -a rrang e Equation (6 ) a bit.           (7)   Or,            (8)   Equation (8) requi re s the  vectors   an d   to have equal proje c tions o n  a pla ne  spa nne d by the colum n  space of  . We observe fro m  Figure 2 that   and    have equa l  proje c tion s o n  a plane o r th ogon al to the se con d  ba sis  vector  .   and   can b e  proj ected on   su ch pla ne b y  a projectio n  matrix of the  form:            (9)   We can subs titute   in Equation (5 ) to solv e for  .            (10 )   Similarly  for  ,            (11 )     will project   and    on a plane ortho gona l to   .   Using  Equation (1 0) and (11), we  can  dire ct ly  solv e  f o r   without inverting the matrix  . Equation (10) and (11 )  also have a   con notation t hat   can be  solved indep e ndently of  .      4. Method   No w we p r e s ent the method for solvin g the gene ral  proble m  of the form   . We   begin by exp andin g  Equati on (3 ),        …     (12 )   Multiplying Equation (12 )  by a matrix  ,        …     (13 )   In order for    to be ze ro,            (14 )   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A New App r o a ch to Lin ear  Estim a tion Problem  in Multi-user …  (Mu ham m ad Ali  Ra za Anjum )   341 Equation (13) becom es,         …     (15 )   Multiplying Equation (15 )  by a matrix   ,          …       (16 )   In order for     to be ze ro,                  (17 )   Equation (16) becom es,           …     (18 )   Contin uing in  the same fa shion,         …  …  …    (91 )   or,         …   …    (20 )   Multiplying bo th side s by  ,        …   …    (21 )     Or,           (22 )     With,          …    (23 )     For the  -th un kno w n,         (24 )     With,         … …  ∃     (25 )       5. Proof  In this  se ctio n, we  provid e the  pro o f o f   the propo se d metho d . We be gin the   proof  by  writing the b a s ic le ast squa res p r o b lem.            (26 )           Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 13, No. 2, Februa ry 2015 :  337 – 351   342 Expanding E quation (26 ) ,        ⋮  …   ⋮      (27 )     …  …  ⋮⋮ ⋱ ⋮ ⋮   …    …   ⋮    (28 )   I f  column s of    are orth ono rmal, then Equation (2 8) b e com e s,         … … ⋮⋮ ⋱ ⋮ ⋮ … …  ⋮       (29 )    ⋮     (30 )   I f  column s of    are orth ogo n a l, then Equa tion (28 )  be co mes,         …  … ⋮⋮ ⋱ ⋮ ⋮  …    …  ⋮       (31 )      ⋮     (32 )   I f  column s of    are n e ither  orthon orm a l  nor o r tho gon al, then the o ff-diagon al te rms i n   Equation  (28 )  p r event the  dire ct  soluti on. If  we  ca n someh o w  eliminate th e s e te rm s, th en a  dire ct solutio n  of the fo rm  (32 )  is po ssib le.  In ord e r to  do that, we i n se rt a bl ock  matrix   matrix  in Equation (26) an d re -write it as:            (33 )   Expanding (3 3),   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A New App r o a ch to Lin ear  Estim a tion Problem  in Multi-user …  (Mu ham m ad Ali  Ra za Anjum )   343    ⋮  ⋮  …   ⋮  ⋮    (34 )    ⋮  …  …  ⋮⋮ ⋱ ⋮ ⋮   …    …   ⋮  ⋮    (35 )   If only,         ∃   (36 )   Then Equ a tio n  (35 )  take s the form,          …  … ⋮⋮ ⋱ ⋮ ⋮  …     …  ⋮     (37 )   And the soluti on be come s,          ⋮       (38 )   For Equatio n (38 )  to hold, we can choo se   to be:          … …  ∃    (39 )     is  a projec tion matrix.            (40 )    proje c ts a ve ctor on a n  axis that  is orth o gonal to the p l ane defin ed  by  . An important  prop erty of   matrix is that  the pro d u c t    is zero. T h is i s  be ca use th e proj ectio n  o f  any vector  on an axis o r thogo nal to itself is alway s  zero. Hen c e,  the prod uct    i s  always  zero.                (41 )   This p r op erty of   matrix can  be can b e  used to eliminat e the off-diag onal entri es i n   Equation (1).       …  …  ⋮⋮ ⋱ ⋮ ⋮ …  …   ⋮  (42 ) Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 13, No. 2, Februa ry 2015 :  337 – 351   344 Starting with  the last term  in first ro w o n  the left hand side of Eq. (42), we mul t iply th e   top row  with  .        …  …  ⋮⋮ ⋱ ⋮ ⋮ …  …   ⋮   (43 )   With,           (44 )   Equation (43) becom es,         …  …  ⋮⋮ ⋱ ⋮ ⋮ …  …   ⋮   (45 )   Similarly, to eliminate    we  multiply the top ro w in Equ a tion (45 )  wit h    ,          … …  ⋮⋮ ⋱ ⋮ ⋮ …  …    ⋮   (46 )   Such that,                  (47 ) We  contin ue  this multipli ca tion in this m anne r until all  the off diago nal entri es i n   the first  row a r e remo ved.        … …  ⋮⋮ ⋱ ⋮ ⋮ …  …   ⋮   (48 )   With   ,         … …    (49 )   And,           …   …    …   …    (50 )   Followi ng the  same proce dure to rem o ve off diagonal entrie s  for the remaini n g  rows of  Equation (48), it become s :  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A New App r o a ch to Lin ear  Estim a tion Problem  in Multi-user …  (Mu ham m ad Ali  Ra za Anjum )   345     …  … ⋮⋮ ⋱ ⋮ ⋮  …    …  ⋮     (51 )   With,         … …  ∃    (52 )   Multiplying bo th side s of Equation (52)  wi th   to revert back  to our leas t s q uares   s o lution as  in  Equation (35),       ⋮  …  … ⋮⋮ ⋱ ⋮ ⋮  …    …  ⋮  ⋮    (53 )   Solving for   in  Equation (53), we obtain Equation (38 ) .         ⋮       (Re peat )     6. Proof of the Choic e  of   Matrix  In this  section, we will  prov ide a novel  factori z ation  of LS solution which confi r ms our   choi ce of   ma trix.   For the s a ke of brevit y, we will provide the proof for   2 . The proof can be   simila rly extended to any d i mensi on. Su bstituting   2  in  Equation (26) and expan di ng,              (54 )        (55 )   Proceedi ng di rectly for the  solutio n ,                (56 )   This would yi eld,                 (57 )           (58 ) Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 13, No. 2, Februa ry 2015 :  337 – 351   346              (59 )   The term     ca n be in  written two  ways.  Firstly, multip ly  and divide it by  ,                       (60 )   Secon d ly, multiply and divide it by  ,                   (61 )   Opting Equati on (60 )  an d Equation (61 )  for first an d se con d  ro ws of  Equation (59) resp ectively,               (62 )   Term s    and    are scal ars. Can c ellin g an d simplifying  Equation (62),                (63 )   The factori z a t ion pro c ess  reveal s the same   matrix  we employe d  in Equation (38 )  as  the solution s obtaine d by  Equation  (3 8) and (63) a r e  exactly same.  This confirms our choi ce of   matrix in Equation (38 ) .        7. Algorithm   In this se ctio n, we presen t an algorith m   for pro p o s ed method.  We will  start  with an   example, say  computation  of  , and onwa r ds b u ild a ge neri c  algo rith m. We begin by re-writing  Equation (15),            (64 )     is ge ne rated  from   by rem o ving its last  colum n . Thi s   last colum n  is used to  construct    whi c h is   then multiplied w  .                  (65 )     and   are the n  update d .   Evaluation Warning : The document was created with Spire.PDF for Python.