TELKOM NIKA , Vol.14, No .2, June 20 16 , pp. 538~5 4 7   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v14i1.3147    538      Re cei v ed  No vem ber 2 5 , 2015; Re vi sed  March 21, 20 16; Accepted  April 15, 201 6  Low Complexit y  Sparse Channel Estimation Based on  Compressed Sensing       Fei Zhou, Yantao Su*, Xin y ue Fan   Cho ngq in g Ke y L abor ator y   of  Optical Comm unic a tion  and  Net w orks, Ch o ngq ing U n iv ers i t y  of Posts an d  T e lecommunic a tions, Ch on g w e n  R oad, 4 0 0 065, Ch on gqi n g , Chin a   *Corres p o ndi n g  author, e-ma i l : s y tgps 200 0 @ 16 3.com       A b st r a ct   In w i reless co mmu n icati on,  chan nel  esti mation is  a key  techno lo gy to receiv e sig nal  precis ely.  Rece ntly, a  ne w  meth od  na med c o mpress e d  se nsin g (C S) has  be en  pr op osed  to  esti mat e  sp arse c h a n nel,   w h ich greatly  improves th e spectru m  effici ency. How e ve r, it is difficult to reali z e   it due to its hi g h   computati o n a l  compl e xity. Althou gh the pr o pose d   Orthog ona l Matchin g  Pursuit (OMP) can reduc e the  compl e xity of CS, the efficie n cy of OMP is still low   beca u se on ly on e i ndex is i d e n tifi ed per it eratio n.  T herefore, to  solve this  prob le m, more effi cient sch emes  are pro pos ed . At first, w e  a pply Ge nera l i z ed   Orthogon al M a tching  Pursu i t  (GOMP) to chann el  esti mati on, w h ich  low e r co mp utatio n a l co mplex i ty  by  selecti ng  multi p le i ndic e s in  each  iter atio n. T hen a more  effective sch e m e th at select s indic e s by le ast   squar es (LS)  meth od  is pro p o sed to s i g n ific antly re duc e t h e co mp utatio n a l co mplex i ty, w h ich is a  mod i fied  meth od  of GOMP. Simul a ti on resu lts an d theor etical  ana lysis sh ow  the effectivity of the prop o s ed   alg o rith ms.      Ke y w ords : ch ann el esti mati o n , compresse d  sensin g, comp utation a l co mpl e xity, index, at om     Copy right  ©  2016 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  The pe rform ance of wireless comm unication co nsid era b ly depen ds o n  wirel e ss  cha nnel.  Du e  to the  comp lexity and va riability of  ge ogra phi cal  e n vironm ent, the p r op agati on  signal is li kely to undergo multipath  pr opagation and Doppl er  shi ft, generating frequency  sele ctive fadi ng and time selective fadin g  whi c h di sto r t the signal  severely [1]. In  orde r to obtain   accurate  re ceipt si gnal, it  is  ne ce ssa ry to ac quire  the exa c t ch annel  state  informatio n (CSI).  Therefore, we need to kn ow the preci s e chan nel im pulse re spo n s e (CIR) firstl y. So  far, cha nnel  estimation u s i ng refe ren c e  sign als o r  pilo ts is  the mo st commo n method to obtain  CIR [2], which   transmits a g r oup of kno w n signal, that  is, referen c e signal s o r  pilots, and th en ca rrie s  o u t  cha nnel  esti mation ba se d on the va ri ation bet wee n  re ceiving  signal a nd tra n smitting  sig nal,   lastly obtainin g  the CIR.   Cla ssi cal  pilot s  b a sed  ch an nel e s timatio n  metho d s in clud e le ast  squares (LS),  minimum   mean squ a red  error (M MSE), and  discrete Fou r ie r Trans f orm  (DFT). Noteworthily,  traditional  method s do n’ t con s ide r  the  spa r sity of wi rele ss  ch ann el, which re sult in huge  waste of spe c trum  resou r ce. Wit h  the  develo p ment of  re search, a   lot of  literatu r e s  have sho w n  that  the wirel e ss  cha nnel s are gene rally sp a r se in p r a c tice. The CS  ba sed  chan nel  estimation util ize s  the cha n nel  spa r sity, re d u ce s the n u m ber  of pilots an d impr o v es the  spe c trum  efficie n cy finally. Many  resea r chers  have pro p o s ed a lot of a l gorithm s su ch as   1 l -no r m  minimization  based Ba si s  Pursuit (BP) algorithm [ 3 ], greedy it eration  ba se d Matchi ng  Pursuit (MP) algorithm  a nd  Orthog onal  Matchin g  Pursuit (OMP)  algorith m  [4 , 5]. BP algorithm has hi gh re con s tru c tion   accuracy, bu t its comput ation co st is huge.  Com pare d  with  BP algorithm , MP algorithm   improve s  the  comp utationa l compl e xity,  but we ak en s   its  r o bu s t ne ss . O M P is  a   mo d i fie d  me th od  of MP algori t hm, which execute s  an  orthog onali z ation of the  sele cted at oms. Th e O M P  algorith m  ca n brin g a fa st co nverg e n c e a nd go o d  rob u stn e ss as  well. In  addition, O M P  algorith m  ha s advantage s  of high re con s tru c tion a c cura cy and co mputation sp eed.   Re cent ly ,  mo st  re se ar che r s  have  paid  their m a in  attenti on on   the improve m ent of  estimation  accuracy. Aimin g  at Ultra  Wi deba nd  (UWB) ch ann el, A.H. Muqaib e l  prop osed m o re   pra c tical  di ctionari e s to  en han ce th e  sp arsity  of UWB ch annel,  a nd the n  im proved the  a c cura cy   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Low  Com p lexity Sparse Ch annel Estim a tion Base d on  Com p re ssed  Sensin g (Fei  Zhou )  539 of received  signal [6]. S. Pramon o ha s imp r oved  t he e s timatio n  accu ra cy throu gh a pply i ng   multiple input multiple  output (MIM O) to  ch annel es timation [7]. In literatures  [8] ,  a  reconfigu r a b le and  spa r se  array a n tenn a wa s propo sed, whi c h  ca n also im prove the estimati on   accuracy. Ad ditionally, ma ny other  re searche r s hav e pu rsued  hi gh e s timatio n  accu ra cy  by  optimiz ing pilots ’ s e ttings  [9, 10].  In fact, the chann el estim a tion accu ra cy has  re ache d a relatively  high level by  utilizing  the existed  a l gorithm s. So  the com put ational  compl e xity of algorithms al rea d y  becom es t h e   main con c ern in pra c tice. However,  up to now, only a few literatu r e s  about re du cin g   comp utationa l complexity have bee n re leased.  A modified OMP (MOMP) was  prop osed in [ 11],   it not only re duces th e co mputational  complexity  effectively, but also h a s  a g ood e s timatio n   accuracy. Bu t it assume s  all cha nnel ta ps di stri b u tin g  adja c ently, whi c h limits it s appli c atio n in  pra c tice. In [12], an expand er graph ba sed CS wa s  propo sed to sp arse ch ann el, which is ben efit   to red u ce the  com putat ional complexity to  (( ) ) OM N N , where  M  and  N  are th e  length o f   pilots an d ch annel, re sp ectively. But the  method in [12] is sen s itive  to noise.   Therefore,  a  further resea r ch  i s  n eede d to   solve th e p r oble m  of  high  comput ationa l   compl e xity.  As mentio ne d previo usly,  OMP algo rit h m ha s adva n tage s of hig h  re con s truct i on   accuracy  and  com putation  sp eed, b u t for p r a c tical  a pplication, its com putation a l complexity  i s   still too hi gh.  Hence, in thi s  pa per, we  do a furt her research  on t he basi s of  OMP algorithm to   redu ce th e computation a l  compl e xity and en su re t he estim a tion  pre c isi on at  the sam e  time.  Firstly, we  a pply Gen e rali zed  Orth ogo nal Mat c hi ng  Pursuit (G O M P) alg o rith m [13] to sp arse   cha nnel e s ti mation, whi c h is a modifi ed metho d  o f  OMP. Owin g to the sele ction of multi p le   atoms p e r iteration, the  calculating  spee d is  i m prove d  an d the estim a tion accu ra cy is  guarantee d a t  the same ti me. The n  ba sed  on th e id ea of  GOMP  algo rithm, a  better al go rith m   named M - G O MP is p r o posed. M-G O MP sele ct s  atoms with  a new p e rspe ctive, avoidin g   repe ating ite r ation s  of th e greedy al gorithm,  whi c h  can  grea tly redu ce th e co mputatio nal   compl e xity. A numbe r of compute r  sim u lation s  are  con d u c ted, showi ng a bet ter com putati on  spe ed an d a good recon s truction a c cura cy of the both algorithm s.   The  re st of t h is  pap er is  orga nized  as fo llows. Se ct ion 2  b r iefly  depi cts th e  CS theory   and the p r o b l e m is  stated i n  Section  3. In Secti on  4, we p r op ose the efficie n t schem es  of in dex  sele ction, na mely, the GOMP and  M-GO MP al gorithm s. Se ction 5 p r e s ent s comp uter  simulatio n s a nd com p lexity analysi s . The con c lu sio n  is dra w n in Se ction 6 finally.  In  this  p ape r,  bold  u ppe r case and bold lowe r ca se  le tters  d enote matrices and vectors,   r e spec tively.  T A  denote s  th e  subm atrix of  A  re stricte d  to  colum n s inde xed by the  se t  T .  H A ,  T A , and  †1 () H H A AA A  denote  the he rmitian  tran spo s ition ,  transpo sitio n , and  pse u d o -inve r se   of matrix  A , res p ec tively.  2 t  d enote s   2 l -no r m  of  t .  , Ah  den otes the in ne r p r o duct  of mat r ix  A  and vector  h .  ˆ h   denote s  the e s timated valu e of  h .      2. Compres s e d Sensing  Bas e d Re co nstru c tion   The p r op ositi on of CS i s  a  revolution ary  brea kth r ou gh  in sign al p r o c e ssi ng. It breaks the  rest rictio n of the Nyqui st sampling th eo rem an d im p r oves th e sp ectru m  efficie n cy greatly [14,   15]. The  pre m ise  of CS  a pplication i s  t hat the  ob served si gnal  is  spa r se o r   co mpre ssible,  whi c h   mean s there are only a fe w non ze ro va lues o r  si gni ficant value s  i n  a gro up of observed  sig nal.   Fortun ately, a lot of  stati s tics a nd  ob servatio n d a ta indi cate  th at the  wirele ss chan nel i s   gene rally sp arse, whi c h l a ys found ation of  the CS applicatio n .  Standard  CS mea s ure m ent  model is give n as follo ws:      rt                                                                                                                                       (1)    Whe r e  r  is a  1 M  observed  vector,   is  a  M N measureme n t mat r ix,  t  is a  1 N   K -s par s e  sign al with  K  non zero valu es,   is a  1 M  noise vecto r  wh ose ele m ent s are additive white   Gau ssi an va riable s . CS i s   mainly abo ut  how to  re co n s tru c t ori g inal  sign al  t  from  the kn own   r   and  . Since  M N  for mo st of the com p re ssive sen s in g scenari o s, reco nstru c ting  t  directly  from (1 ) is  an  unde rdete r m i ned p r obl em. Fortun ately,  that sign al is  spa r se ma ke s it possibl e to   solve thi s  p r oblem. T he l i terature [16]  pointed  out  that if   satisfies Restri ct ed Isometry   Prope rty (RIP ), then  t  can b e  recon s tru c t ed accu rately . We write  RIP as lemma 1 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  538 – 54 7   540 L e mma  1 : Fo r any  K -sparse sign al  t , if there exists a con s tant  (0 , 1 ) K  s u c h  that:  22 2 22 2 (1 ) ( 1 ) KK   tt t                                                                                                              (2)    Then   sat i sf ie s RI P .   In the algo rit h ms  pro p o s e d  in this  pap er, the n u mb er of me asurements  M  is a very  important fac t or. If  M  sat i sf ie s:     2 (1 ) ( 1 ) l o g 1 N MK K K                                                                                                               (3)     Whe r e  (0 ,1 )  is  a  c o ns tant, then obey s the  RIP con d ition  with overwh elming p r ob a b ility  [17]. This i s  t he lo we r bo u nd of  M  on th e  pre m ise of  accurate  re constructio n . Ho wever,  the  magnitud e is not given in [17], so the exact lower bo u nd of  M  is not determin ed eit her.    With num ero u s exp e rim e n t  analyse s , Tropp a nd  Gil b ert pointe d  o u t that we  ca n re cove r  t  from (1)  with large p r o babil i ty if  M  is expre s sed a s  follo ws [18]:     lo g M KN                                                                                                                                                    (4)      3. Problem Statement  Con s id er a  M  pilots ,  N  length  and  K -spa rse  cha nnel  sy stem. The  po si tions  of pilo t s   are de noted  by 01 1 ,, , M kk k . CS based  sparse  cha n nel estimatio n  can b e  expressed a s :     MN  yX F h                                                                                                                                            (5)    Whe r e,  01 1 [( ) , ( ) , , ( ) ] M d i a g xk xk xk X  is the diago nal matrix  of transm i tted pilots.  01 1 [( ) , ( ) , , ( ) ] T M yk yk y k y  and  [( 0 ) , ( 1 ) , , ( 1 ) ] T hh h N  h are the   1 M  received pi lot vector  and  1 N spa r se chann el vecto r , resp ectively . There  are  K n onzero val u e s  in  h .   is a  1 M   compl e x addi tive white Ga ussian n o ise vector.  M N F  is a  M N  partial Fo uri e r matrix, whi c h is  obtaine d by  sele cting  the  ro ws of  Fo urie r m a trix  with in dices  01 1 ,, , M kk k .  M N F  can  be   expre s sed a s :    00 0 11 1 11 1 01 ( 1 ) 01 ( 1 ) 01 ( 1 ) MM M kk k N VV V kk k N VV V MN kk k N VV V ff f ff f ff f          F                                                                                                 (6)    Whe r e e xp( 2 / ) p kq Vp f jk q V  ,  V  is a positive integer,  01 pM  ,  01 qN  . Let  M N AX F , (5) ca n be written as:      yA h                                                                                                                                                      (7)     Whe r e,  12 [, , , ] N A aa a  is a  M N  matrix.  i a  is the colum n  of matrix  A . Comparin g (7 ) with   (1), we   can see  that  y ,  A ,  h  are the  ob serv ed ve ctor, m easure m ent  matrix an d  sp arse  sign al   in CS,  re spe c tively. After obtaining  the  o b se rved ve ct or  y , by ad opti ng a  certain   algorith m , we  can recon s tru c t the cha nne l  h  from  y .  The OMP al g o rithm i s  a commen dable  method fo r chann el re co n s tru c tion. It is one of   the g r eedy  a l gorithm s,  wh ich  ca n effici ently and   sta b ly  re cove r sparse sig nal from  o b serve d   value. The followin g  is the  detailed  step s of the OMP algorith m .    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Low  Com p lexity Sparse Ch annel Estim a tion Base d on  Com p re ssed  Sensin g (Fei  Zhou )  541 Algorithm 1: OMP Algorith m   Input : receiv ed pilots  y , measu r em ent matrix  A , s pars i ty  K , noise va riance  2 .  Initializ e : resi dual  0 ry , estimated su ppo rt se t  0  , iteration co unt  1 t .  Repe at : Ass u me in the  th t  iteration   1:  1 kk  .  2: Identification:  1 arg m ax , , tt j j j  ra a A .  3: Support M e rge r :  t1 {} tt  .  4: Estimation: utilize the LS method:  1 ˆ () tt t HH t  hA A A y .  5: Resi dual  Update:  ˆ t tt - r y Ah .  Until :  2 2 t r  or  tK .  Outpu t : outp u t the estimat ed value  ˆ h .    Carefully stu d ying the  O M P algo rithm ,  we  can  fin d  that the mo st important  p a rt of the  whol e al gorit hm i s  to fin d   the  K  atoms correspon ding  to n onzero v a lue s  in  chan nel  h , which  can b e  call ed  as matching  atoms. As lo n g  as the  K  matchin g  atom s are fou nd, we  can a c hiev e   th e  ac cu r a te   r e co ns tr uc tion  o f   h  thro ugh   LS metho d  gi ven in  step  4.  At the  sam e   time, the mo st  time of the O M P algorithm  are spe n t on see k in g  matching atom s, namely,  the identification st ep,   whose effici ency is quite low. We illuminate it by (8):    12 ,, , a r g , 1 , 2 , Ni t i Ci N    ra                                                                                (8)    Whe r e  C  is an colle ction  of  N  indice s a nd one in dex  in  C corre s po n d  to one ato m  in  A .  Gene rally, th e value   N  is la rge,  so  obtai ning  C  by  step 2  will cost  pl enty of time. However,   even so, OM P algorithm d oesn’t make f u ll use of  C . In each iteratio n, only one of the biggest  indices is se lected  with  the oth e r ind i ce s a ban do ned  co mplet e ly, whi c h  n o t only  wa stes  resou r ce, but  also m a kes  the algo rithm  conve r ge  sl owly. With th e increa se  of iteration s , the   disa dvantag e s  of the OMP algorith m  are  more hi ghligh t ed.      4.   Efficient S c hemes o f  Indices Selecti on  Before giving  the prop osed  scheme s , we  fi rstly pre s ent  two theore m s as follo ws:  Theo rem  1 : In the  algo rith m of this pa p e r, the  sel e ct ed in dice s  ,, ii t iN   will not   be sel e cte d  in the later iteration.  Proof : The th eore m  1 sh o w s that when  the iter ation run s , we do n' t have to worry about  the sele cted  atoms to be  selecte d  agai n ,  includin g  the non-matchi ng atoms.   For the  conv enien ce  of de scription  of th eore m  2,  we  give an  expre ssi on of th e l o catio n   of matching a t oms at first.    {0 , } i Ti h i N                                                                                                                                       (9)    Whe r e  i h  is a tap of cha nnel   h .  Theo rem  2 : (Assu ming the r e ha s b een  execute d   K  iteration s  in tot a l): The  cha n nel  h   can  be  pe rfe c tly re con s tru c ted  wh en th e re sultin g  su pport  set  K  an d the m a tchi ng atom s  set   T  s a tis f y relation as  follows :     K T                                                                                                                                                            (10)     Specifically, (10) ha s two  meanin g s: 1 )  The su ppo rt set  K  must cont ain all eleme n ts of   the mat c hing  atom s  set  T . 2) Th e sup p o rt  set   K  may co ntain  othe r ele m ent s b e sid e s th e   matc hing atoms  set  T .    Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  538 – 54 7   542 4.1. GOMP Algorithm  The propo siti on of GOMP  algorithm  efficiently  improves the d e ficien cy of the OMP   algorith m . Different from t he OMP alg o r ithm, the G O MP algo rith m sele cts  n ( 1 n ) atoms p e r  iteration, that  is, sele cting   n  indi ce s f r o m   C . Then  G O MP pe rforms  spa r se e s timation  an d   resi dual  up da te. In this wa y, we  ca n n o t only m a ke fu ll use  of the  i ndices colle ction  C , but al so   accele rate th e co nverg e n c e of algo rith m, and imp r o v e the algo rithm efficien cy  as a  wh ole.  We  have lemma  2 with re spe c t to the value  n .  L e mma  2 : (GOMP algo rith m): Supp ose   sele cting  n  ato m s p e r ite r ati on, then the  GOMP  algorith m . Ca n reali z e reco vering the o r i g inal sparse  cha nnel u nde r con d ition:     mi n { , } M nK K                                                                                                                                           (11)     Whe r e  K  and  M  are the  spa r si ty of channel  and the num b e r of pilots, re spe c tively [13].  The wh ole p r oce dure of the GOMP algo rithm is sket ched a s  follows:    Algorithm 2: GOMP Algori t hm  Input : receiv ed pilots  y , measure m ent  matrix  A , s pars i ty  K , noise varian ce  2 , the  numbe r of ind i ce s sel e ctio n  per iteratio n  n .  Initializ e : resi dual  0 ry , estimated su ppo rt se t  0  , iteration co unt  1 t .  Repe at : Ass u me in the  th t  iteration   1:  1 kk  .  2: Identification:  S  indice s o f  the  n  highe st amplitude  co mpone nts of  1 T t A r .  3: Support M e rge r :  t1 t S  .  4: Estimation: utilize the LS method :  1 ˆ () tt t HH t  hA A A y   5: Resi dual  Update:  ˆ t tt - r y Ah .  Until :  2 2 t r  or  tK .  Outpu t : outp u t the estimat ed value  ˆ h .    T o  mak e  it ea s i er  to  u n d e r s ta nd , w e   g i ve the sche matic representation of th e GOMP   algorith m  in Figure 1.       C 1 () tt t HH  A AA y 1 T t A r ˆ t t A h y 1 t r t ˆ t h ˆ h ˆ t t A h C o rre l at i o n O p erat i o n Ch oo se I n dices   o f  t h e L a rge s t  Value s   o f   n C E s tim a t ion R e m e as u r e m ent S 1 t t1 t S  S u pp ort Merg er   Figure 1. Sch e matic represent ation of the GOMP algo rithm       Comp ari ng th e GOMP algo rithm with the  OMP algorit hm, we find that the most  different   part i s  th e  step 2,  whi c h  i s  the  core  co mpone nt  of t he G O MP  algorithm.  Note worthily,  becau se   more th an o n e  atom i s  sel e cted i n  ea ch  iterati on,  we  inevitably put  the non -mat chin g atom s i n .  Even so, con s ide r ing th eorem 2, we  still can  re co ver  the sp arse  ch annel a c cu rat e ly. In addition,   becau se the GOMP algo rithm sele cts  n  atoms pe r iteration, gene ral l y, the sparse  chan nel ca n   be re con s tructed with  / Kn  loop s, whi c h grea tly saves the runni ng time  of algorithm.     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Low  Com p lexity Sparse Ch annel Estim a tion Base d on  Com p re ssed  Sensin g (Fei  Zhou )  543 4.2. M-GOM P Algorithm   Based  o n  the  idea  of  GOM P algo rithm,  we  propo se  a  more  efficien t schem e, tha t  is, M - GOMP algo rithm. Compa r i ng the GOM P algorithm wi th the OMP  algorith m , we  can se e that the  key of th e two alg o rithm s  i s  to  se arch t he mat c hin g   atoms. A s  lo ng a s   all the  matchin g  ato m s  are a c qui red,  we ca n achi eve accurate recon s tru c tio n  by the step 4 of the OMP algorithm o r  the   GOMP algo ri thm. Hence, the most critical thing  now i s  ho w to get all the matchi ng atoms  with  no pl entiful ti me  co sting  at the  sam e  tim e . Co nsi deri n g the  sim p licit y of LS al gorit hm, we u s e  the  LS algo rithm  to se arch  ato m s, a nd th en  estima te  the  sp arse  ch an nel by th e  step 4  of G O M P ,  whi c h g ene rates the  M-GOMP alg o rithm. T he d e tailed impl e m entation of  the M-GO MP  algorith m  is shown as follo ws:     Algorithm 3: M-GO MP Algorithm   Input : receiv ed pilots  y , measu r em ent matrix  A , s pars i ty  K .  Initializ e : esti mated su ppo rt set   .  Begin :   1: Identification: solving a  simple LS e s t i mation  1 0 ˆ hA y , let  indices of the  K    highe st ampli t ude com pon ents of  0 ˆ h .  2: Estimation: utilize the LS method to re con s tru c t:  1 ˆ () HH  hA A A y   End   Outpu t : outp u t the estimat ed value  ˆ h .    Comp ari ng M - GOMP al gorithm with the  OMP and G O MP algo rith ms, we  can  see that  the M-G O MP  algorithm i s   quite differe n t  fr om the O M P and GO MP algorithm s. The M - GO MP  algorith m  o n l y  has two  st eps with  ide n t ificati on a n d  estim a tion,  and  wh at’s  more, th ere i s  n o   loop s in M-G O MP. For the convenie n ce  to understan d, we give the schemati c  repre s e n tation  of  the M-GO MP algorithm in  Figure 2.      1 Ay 0 ˆ h 0 Choo se  I ndic e s   of   the ˆ La r g e s t  V a l u e s  o f   K  h 1 () HH  AA A y ˆ h y LS  E s t i ma t i o n Ch a nne l  Re c onstru c t i on     Figure 2. Sch e matic representat ion of the M-GO MP algorithm       From Fig u re 2 we can see  the M-GOM P algorit hm p e rform s  o n ly one iteratio n from left   to right. Hen c e it can g r e a tly improve the efficien cy of reco nstru c tion. In term s of estimati on   pre c isi on, be cau s e  we  ca n acquire the  requi re d  K  atoms from e s t i mated  0 ˆ h , we are a b le t o   reali z e a c curate recon s tru c tion by the step 2 in M-G O MP.   In this p ape r,  we  also a d o p t the comm only used  LS algo rithm a n d  the hi gh  accuracy   estimated M M SE algorith m  as the refe ren c e s  of per forman ce an alysis. He re,  first of all, we put  down their ex pre ssi on s as  follows:    1 ˆ () HH LS hA A A y                                                                                                                                   (12)    21 1 1 ˆ (( ) ) H MM S E   HH H H hR R A A A y                                                                                             (13)    W h er e  H H R  den otes th e  aut ocova r ian c e   matrix of  ch annel  vecto r   H ,  H  is th e fre quen cy  domain rep r e s entatio n  of  h  and   denotes  the stand ard  deviation of n o ise.       5. Simulations and An aly ses   In this sectio n, the Mean  Square Error (MSE)  simul a tion, run n in g time sim u la tion an d   compl e xity analysi s  are d e scrib ed to verify  the goo d perfo rma n ce of the pro p o se d GOMP  and   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  538 – 54 7   544 M-GO MP alg o rithm s . The  classi cal m e thod s su ch  as LS algo rithm, MMSE  algorith m , OMP  algorith m  are  also a pplied f o r co mpa r iso n  at the same  time.        5.1. MSE Si mulation  In this  simul a tion, we  con s ider  a  spa r se  ch ann el  with  length   496 N , s pars i ty  12 K ,  and utilize G aussia n  pilots, who s e nu mber is d e te rmine d  by (4). In order to  guara n tee the   accurate re constructio n , we choo se  256 M . The noi se i s  compl e x ad ditive white  Gau ssi an  noise. Additionally, consi d ering the lem m a 2, we  ch oose the nu mber of indi ces sele ction with   2, 5 , 9 n  in GO MP alg o rithm. In o r d e r to  avoid th e interfe r en ce  ca used by  ra ndomi c ity of signal ,   we ado pt the idea of taking  average with  multip le loop s. In addition, normali zed  MSE is adopted   in the simulati on. The sim u l a tion re su lts  are sho w n in  Figure 3 and  Figure 4.  Figure 3 i s  th e MSE simul a tion un der  di fferent SNR. As can b e  se en from  Figu re 3, the  MSE curve s  of different  algorith m s  decrea s e  wh en the SNR increa se s, whi c h me an s a n   improvem ent  of cha nnel  recon s tru c tio n  accu ra cy. Additionally, comp ared  wi th the cla s si cal   algorith m s, th e recon s tru c tion a c cu ra cie s  of   the prop ose d   G O MP and M-G O M P   algo rithm s  are   not only fa r b e tter, but  also very  clo s e t o  the  OMP al gorithm. Eve n  when   2 n , the MSE c u rv e  of GOMP alg o rithm  compl e tely catch e s up with that   of OMP algo rithm. All of th ese d e mo nstrate   the effectivity  of the propo sed algo rithm s .      Figure 3. The  compa r i s on  on MSE with  varying SNR  Figure 4. The  compa r i s on  on MSE with  varying sp arsity                                                                     Figure 4 i s  th e MSE perfo rmance si mul a tion with  va rying sp arsity. From Fi gu re  4, we  can  see tha t  the chann el re con s tru c tion a c cura cy decre ase s  with  K  increasi ng. T h i s   phen omen on  can b e  expl ained by the  increa se  of chann el den sit y . When the  cha nnel d e n s ity  increa se s, th e num ber  of  signifi cant tap s  be co me s  la rge r . Ho weve r, the nu mbe r  of pilots  doe sn’t  increa se at t he sa me tim e , which ma kes u s   not a b l e  to get eno ugh chan nel  informatio n a n d   lead s to the  increa se of e s timated e r ro rs finally . It’s worth  noting  that with the increa sin g  of  spa r sit y   K , although th e pe rforma nce of the propo se d  algorith m s i s   decli ned, the  MSE curv e s   of the propo sed al gorith m s have foll owe d  the O M P well all the time. It i m plies  both of the  prop osed alg o rithm s  have  robu stne ss a gain s t differe nt chan nel  sp arsity. In addi tion, from Fig u re   3 an d Fig u re  4, we  can  see that th e e s timati on  accura cy of the   MMSE algo rithm is the  be st.   Ho wever, d u e  to its high  comp utationa l compl e xity,  we generally  can’t utili ze it in practice. But   we can take the MSE curv e of MMSE algorithm a s  th e lowe r bou n d  of estimatio n  accuracy.   Combi n ing F i gure 3  with  Figure 4, we can  con c l ude that the  MSE of the  GOMP   a l g o r ithm be co me s  w o rs e  w i th  th e inc r ea s e  o f   n . This  is m a inly because  when  n  is larger, the  GOMP algori thm will involve more nonmatching at oms. Theoreti cally, we  can utilize (16) to   demon strate. When the value  n  is larger, the value   2  in (16) ca nnot be igno red, wh o s e   0 5 10 15 20 25 30 10 -8 10 -7 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 S NR( d B ) MS E     LS OM P GOM P  n = 2 GOM P  n = 5 GOM P  n = 9 M - GOM P MM SE 4 8 12 16 20 24 28 10 -8 10 -7 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 S par s i t y  K MS E     LS OM P GO M P  n = 2 GO M P  n = 5 GO M P  n = 9 M- G O MP MMS E Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Low  Com p lexity Sparse Ch annel Estim a tion Base d on  Com p re ssed  Sensin g (Fei  Zhou )  545 existen c e lea d s to the de cline of e s tim a ted accu ra c y .  H o w e v e r ,  i t  i s  a l s o  l i k e l y  t o  s h o w  u p  a   spe c ial  ca se.  When th e value  n  is sma ller, the co rresp ondi ng M SE is highe r, as sho w n i n   Figure 3. It is be ca use th e GOMP  alg o rithm  with  smaller  n  executes m o re  times  of iterati on,  and then p u ts more no nma t ching atom s  in.    5.2. Running  Time Simulation   In this  se ctio n, we  mainly  co nsid er th e  run n ing tim e  sim u lation  with varyin g  cha nnel   length. T he  simulatio n  p a r amete r s a r e  set  a s   SNR 5 dB ,  51 2 M ,  12 K , the  s i mulation  results  are  sh own i n  Fig u re  5. Du e to the  high  co mple xity of MMSE algo rithm, we don’t  co nsi d e r   the MMSE algorithm in the  simulation.   As is sh own in Figure 5, comp ared wit h   the OMP algorithm, the  prop osed alg o rithm s   have go od p e rform a n c e.  Among them,  the GOMP  algorith m  wit h   5, 9 n  co st only  about  1/ 2   runni ng time  as mu ch  as t hat of the O M P algorith m , namely, the y  can  save th e run n ing tim e  by  more tha n  50 %. What’s m o re, the M-G O MP algorit h m  can save the run n ing ti me by more than   85% un der di fferent chan n e l length s ,  which  proves  the M - GOMP   algorith m  to b e  mo re  sup e rior.  These sig n ificant improvem ents mainly o w e s  to  the efficient sch e me s of indices  selectio n.   Beside s, the averag e iterat ions  simulatio n  with  varying  sparsity is al so given in Fi gure 6.   From Fig u re  6 we ca n se e ,  the average  iterati ons of the pro p o s ed  algorith m s a r e less than that  of the OMP  algorith m  un der diffe rent  spa r sity.  The  com putation a l com p lexity of algo rithm  is  clo s ely  relate d to th e n u m ber of ite r atio ns,  so  t he  si mulation  re su lts of  Figu re  6 not  only ve rify   the su peri o ri ty of the GOMP and M - GOMP  algo rithms  agai n, but also d e mon s trate t h e   robu stne ss of both algorith m s at the sa me time.      Figure 5. The  compa r i s on  on run n ing ti me with  varying ch an nel length     Figure 6. The  compa r i s on  on avera ge  iteration s  with  varying spa r sity      5.3. Comple xit y  Analy s is   In this sectio n, we  an alyze the  comput ational  com p l e xity of the  GOMP  and   M-GO MP  algorith m s, t o  p r ove th e  sup e rio r ity of  the t w o  alg o rithm s  q uan titatively. The  literature  [ 13]  pointed   out that  the co mputational  compl e xi ty  of  GOMP alg o rithm ca n be  a pproxim ately  expre s sed as  22 2( 2 ) GO MP Cs M N n n s M  , wh ere  s  is t he n u mbe r   of iteratio ns. B e ca use th e   OMP alg o rith m is a  sp eci a l ca se  of th e  GOMP al go rithm  with  1 n , the c o mplexity of the OMP   algorith m  can  be exp r e s se d as  2 23 OMP CK M N K M  . In [13], a multiplication an d an  a ddition   are  re garded  as a  ba sic o peratio n, respectively.  Ba sed  on  the  same p r in ciple ,  we  discu s s  the   comp utationa l complexity of the M-GOM P algorithm.   Identification :  This ste p  ha s high  com p l e xity due to the involveme n t of matrix inversi on,   so  we figu re  out the  cha n n e l freq uen cy resp on se  H  first l y, and then  convert  H  to time dom ain   by IFFT. By this way, the total numbe r o f  operation s  i s   2( 2 1 ) M MN . In addition ,  0 ˆ h  need s to   be so rted to find  K  best indi ces, whi c h req u ire s   (( 1 ) ) / 2 NK K K  ope rati ons.   1 2 4 6 8 10 12 14 16 0 0. 01 0. 02 0. 03 0. 04 0. 05 0. 06 0. 07 0. 08 C han nel  L e ngt h  L ( x 62) R u nn i n g Ti m e ( s )     OM P M- G O MP GOM P  n = 2 GOM P  n = 5 GOM P  n = 9 4 8 12 16 20 24 28 0 5 10 15 20 25 30 S pars i t y  K A v erage  I t e r at i o n s     OM P GO M P  n = 2 GO M P  n = 5 GO M P  n = 9 M- G O MP Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  538 – 54 7   546 Es timation : This  step i s  al so involved  wit h  matrix  inversion, therefore, we  utilize t he QR  factori z ation  and mo dified  Gram -Schmi dt (MGS)  alg o rithm to get  a fast solutio n , whi c h lea d s  to  a c o mplexity  with  23 2 25 4 K MK M K K K  .  The whole  M-GO MP algorithm o n ly has o ne  iteration,  so i t s total com putationa l   compl e xity can be app roxi mately expre s sed a s   2 22 MG O M P CM N K M  .  No w let’s discu ss the com putational co mplexity  of th e three algo ri thms. Noting  that the   value  s  and  n  of GOMP algorithm a r e  small con s ta nts, so the compl e xity of the GOMP  algorith m  ca n be exp r e ssed a s   () Os M N , and  the co mplexit y  of the OM P algorith m   can  be   expre s sed as  () OK M N . As can b e  see n  fro m  the Fig u re  6,  the value  s  usually tend s t o  be   smaller than  K , that is to  say, the G O MP algo rit h m ha s g r e a t advantag e s  in te rm s  of  comp utationa l complexity. Additionally, becau se  K<M, M<N , the  comp utationa l complexity o f  M- GOMP alg o rit h m can be  e x presse d a s   () OM N . Obviou sly, the M-GOMP  algorith m  that  we p u t  forwa r d h a s a  better perfo rmance.      6. Conclusio n   In this pa pe r, in view o f  the high com putation a l  compl e xity of existing  chann el  estimation m e thod s, we a pply GOMP algorith m  to spa r se ch an nel estimatio n . Meanwhile , a  more  effectiv e sch e me  na med M - G O M P  algo rithm i s  p r o p o s ed  b a se d o n  the   idea  of GO M P   algorithm, which selects m u ltiple indi ces in eac h ite r a t ion. Compa r ed with the  OMP algo rithm,  comp uter sim u lation s an d  theoreti c al  an alysis sh o w  t hat the  pro p o s ed  two  algo rithms not  on ly  have goo d e s timation a ccura cy, but also can g r eat ly redu ce th e run n ing ti me req u ired  for   cha nnel e s ti mation. Esp e c ially the M-GOMP alg o rit h m,  as a  re su lt of efficient scheme  of in dice s  sele ction, it  can  save mo re tha n  8 5 %  of t he  run n i ng time.  Con s eq uently, G O MP alg o rith m,  esp e ci ally the M-GO MP algorith m  is  expec te d to be a co mpet itive candid a t e sch eme f o r  cha nnel e s ti mation in wi reless commu nicatio n .      Ackn o w l e dg ements   This  work was su ppo rte d   by  th e National Natu ral  Sci e n c e Found ation  of  Chi na  (614 710 77,  6130 1126 ), t he Fu ndam e n tal and  Frontier  Re se arch Proje c t of Ch ong qi ng  (cstc2013j cyj A 40034,  cstc2013j cyjA400 41), th e S c ie nce  an d T e chnolo g y Proj ect of  Chong qin g   Munici pal Ed ucatio n Com m issi on (K J1 4004 13).       Referen ces   [1]    Hla w a tsc h  F ,   Matz G. W i rele ss commu nicat i ons  over  ra pid l y time-var yi n g  cha nne ls. US A: Academ ic   Press. 2011: 1 99-2 36.   [2]    Baoka i  Z u , Xin y u an  Xia, Ke w en  Xi a, Chu a n j i an B a i. Ch an n e l estimati on  o n  60GHz  w i rel e ss s y stem   base d   on s ubs pace  p u rsuit.  T E LKOMNIKA Indo nesi a n  Jo u r nal   of El ectric al E ngi ne erin g . 20 14;  12(9):   685 2-68 59.   [3]    Jianz hon g Hu a ng, Berger C R ,  Shengl i Z hou , Jie Huan g.  Comparis on of b a sis purs u it al gorith m s for   sparse ch an nel  estimati on i n  u nderw a ter aco u stic OF DM . OCEANS 2010 IEEE. S y dney .  2010: 1-6.  [4]    T eng Sun, Z h i qun S o n g , Yo ngji e  Z h a ng.  Matchin g  purs u it bas ed s par se cha n n e l est i matio n  usi n g   pseu dora n d o m  seque nces . Gl oba l S y m posi u m on Millim eter  Waves (GSMM). Harbin. 20 12: 33-3 7 .  [5]    Aboutor ab N,  Hardj a w a na W ,  Vucetic B.  Ap plicati on  of co mpr e ssive s e n s ing to c han ne l  estimatio n  of  high mobility OFDM system s . IEEE  International Confer ence on  Com m unic a tions (I CC). Budapest .   201 3: 494 6-49 50.   [6]    Muqa ibe l  A H , Alkh od ar y M T . Practical  a pplic atio n  of  compressiv e  s ensi ng t o  u l tra- w i d e b a n d   chan nels.  IET  on Co mmunic a tions . 201 2; 6( 16): 253 4-2 542 .  [7]    Pramon o S, T r i y on o E. Perfor mance  of  channel  estimation in MIMO-OFD M s y stems.  TEL K OMNIKA  T e leco mmunic a tion C o mputi n g Electron ics a nd Co ntrol . 20 13; 11(2): 3 55- 362.   [8]    Morabit o  AF , Iserni a T ,  Donato LD. Optimal s y nthes is of phase- onl y re conf ig urab le l i near sp ars e   arra ys  h a vin g  uniform- ampl itude e x citati ons .  Progress i n   Electro m a gneti cs Rese arch . 201 2;  12 4(1):   405- 423.   [9]    Xu e y u n  H e , R ongfa n g  So ng,  W e ipi n g  Z hu.  Pilot  all o cati on  for sp arse  ch ann el  estimati on  in MIMO- OFDM sy stem s.  IEEE  Transa c tions on C i rcu i ts and Syste m s II: Express Briefs . 2013; 6 0 ( 9 ): 612-6 16.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Low  Com p lexity Sparse Ch annel Estim a tion Base d on  Com p re ssed  Sensin g (Fei  Zhou )  547 [10]    Xi an g R en, W en  Che n , Me i x ia T ao,  Xi aofei  Sha o .  C o mpr e ssed  ch ann el  esti mati on  w i th j o int  pi lot   sym bol and pl acem ent desi g n for high  m o bility OFDM system s . Intern ation a l W o rks hop  on Hi gh   Mobil i t y  W i re le ss Communic a tions (HMW C). Beiji ng. 20 14: 38-4 2 .  [11]    Ziji  Ma, Hon g li  Liu,  H i g a shi n o   T, Okada M, Furud a te H.  Lo w - compl e xity c han nel  esti mation for IS DB- T  over dou bly- selectiv e fadi n g  chan ne ls . Internati ona l S y mposi u m on Intelli ge nt Sign al Process i ng   and C o mmun i c a tions S y stems  (ISPACS). Naha. 201 3: 114- 118.   [12]    Junji e  P an, F e ifei Ga o.  Efficient ch an nel   estimatio n  us i ng ex pa nd er  grap h b a sed   compressiv e   sensi n g . IEEE International Conferen ce on Communications (ICC) . S y dney . 2014: 4542-4547.  [13]    Jian W a n g , K w on S, Shim B.  G enera lize d  or thogo na l matchin g  purs u it.  IEEE Transactions on Signal  Processi ng . 20 12; 60(1 2 ): 620 2-62 16.   [14]    Can des EJ, R o mber g JK, T ao T .  Robust uncerta int y  pri n cipl es: e x act  sign al rec onstr uction from  h i gh ly  i n co mp le te   frequency  information.  IEEE Transactio n s on Infor m ati on Theory . 2 0 0 6 ; 52(2): 48 9- 509.   [15]    Can des EJ, W a kin  MB. An  int r oducti on to  co mpressive  sam p lin g.  IEEE Signal Process i ng Maga z i ne .  200 8; 25(2): 21 -30.  [16]    Can des EJ. T h e restricted is o m etr y  pr oper t y  and its imp lic ations for com p resses se nsi n g.  Co mptes   R e nd u s  Ma them a t iq ue . 200 8; 346(9): 58 9-5 92.   [17]    Baran i uk  R, D a ven port M, D e Vore  R, W a ki n M.  A sim p l e   proof  of the  re stricted is omet r y   pro pert y  for   rand om matric es.  Constructiv e  Approx i m atio n . 2008; 2 8 (3): 253- 263.   [18]    T r opp JA, Gilb ert AC. Sig n a l   recover y  fr om  rand om me asu r ements vi a  orthog on al m a tch i ng  purs u it.  IEEE Transactions on Infor m a t ion Theory . 2 0 07; 53(1 2 ): 465 5-46 66.     Evaluation Warning : The document was created with Spire.PDF for Python.