TELKOM NIKA , Vol.11, No .1, Janua ry 2013, pp. 213 ~22 6   ISSN: 2302-4 046           213     Re cei v ed O c t ober 1, 20 12;  Revi se d No vem ber 29, 20 12; Accepted  De cem ber 5,  2012   Lebesgue-type Inequality for Orthogonal Matching  Pursuit for  μ -coherent  D ictionaries       Ye Peixin*,  Wei Xiujie  Schoo l of Math ematics an d L P MC, Nanka i  Univers i t y , T i anjin  300 07 1, Chin a   *corres pon di ng  author, e-mai l y e p x @n anka i .edu.cn       A b st r a ct   In this paper,  w e  investigate  the efficiency  of so me ki nd  of Greedy Algorith m s w i th respect t o   dictio nari e s fro m  H ilb ert spac es. W e  establ i s h id eal   Le be sgue-typ e  in eq uality for Orth ogo nal M a tchi n g   Pursuit a l so kn ow n in l i teratur e  as the Orth o gon al Gree dy  Algorit h m  for   -coher ent dicti o nari e s. W e  sho w   that the Orthog ona l Matchin g   Pursuit prov ide s  an al most opt imal a pprox i m a t ion on th e first  [1 / 2 0 ]  .    Ke y w ords ort hog on al match i ng pursu it  (OMP),  orthogo n a l gr eedy  al go rithms, b e st  m -t e r m ,  Le be sgu e - type ine q u a liti e s, dictionar ies      Copyrig h ©  2013  Univer sitas Ahmad  Dahlan. All rights res e rv ed.       1. Introduc tion  In this paper  we co ntinue t o  study the conver g e n c e o f  greedy algo rithms with re gard s  to   dict ion a rie s  w i t h  small coh e r en ce ( s ee [ 1 -9] ) .  T he pu rp ose of the re search of app roximation with   rega rd  to in coherent  dictio narie s wa s to  apply  in  co mpre ssed  se nsin g. In [1,  8, 10,  11], it  wa sho w n th at the Orth ogo nal  Matchi ng Pu rsuit i s  effe ctive for si gnal  recoveri ng. In  this pa pe r, we  will discu ss t h is problem  from the poi nt of vi ew of Approximati on Theo ry. We obtain u pper  estimate for  the error of approximatio n by  OMP in terms of the error of the be st  m -ter approximatio n. This arti cle  is a develop ment of re cen t  result s obtai ns by Eugen e  Livshitz in [1 2].  Let us recall t he stan dard d e finitions of G r eedy Algo rithms. We say  that a set  D  from a  Hilbert Space H is a dictio nary  if    || | | 1 , . and span H   DD      The co he ren c e of a diction a ry is define d  as    ,, :s u p | , | D        (1)     Dictio nari e s with  co heren ce  are call ed  - c oh er e n t ORT H O G O N AL MATC HIN G  PU RSUIT  ( O MP) Set 0 :, f fH an d 0 (, ) : 0 OMP f D .   For ea ch 0 m , we can find a  1 m g D  su ch t hat    1 |, | s u p |, | mm m g f gf g  D  ,  and defin e     11 1( , , ) (, ) : ( ) , m ms p a n g g OMP f Proj f D      11 :( , ) . mm ff O M P f   D      The be st  m -term approximation for a funct i on  , f H  is define d  as  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  213 – 2 2 6   214 ,, 1 1 () : ( , ) : i n f .   ii m mm i i ci m i ff f c  D D      Suppo se that  dictiona ry  D  is  -co h e r ent an 1 1 (1 ) . 2 m  It is  well k n own (s ee [3,4] ) that   if   f H  is  m -sparse,  that is  (, ) 0 m f D , then    (, ) . m fO M P f D    (2)     More over, Te mlyakov an d  Zheltov sho w ed that if 1 1 (1 ) 2 m  , then eq uality (2) d o e s  not  hold for all  -coherent dictio narie D  and all  m -spa r s e f   1 1 ,( ( ) 1 ) , : ( , ) 0 , 2 m mf H f O M P f   DD D    (3)     (, ) 0 . m f D      Followi ng T e mlyakov, we recall result s of  L e b e s gue ty pe inequalitie s  whic con n e c ting the error of  Gree dy app roximation an d the best  m -term ap proxi m ation. The s e   inequ alities d o  hold not for all  m , but only  for  () mC ; they provide an estim a te for the  quality of app roximation of  A(m) iteration  of OMP by th e best  m -term approximatio n:     () (, ) ( ) ( , ) , ( )   Am m fO M P f B m f m C DD    (4)      with s o me  () , ( ) , ( ) Am B m C   The first Leb esg ue type inequality for Greedy Algo rithms was obt ained by Gilb ert et al.  in [3] They establish ed (4 ) for an optim al  () : , A mm  an orde r-opti m al    1 () 1 , 82 C       and fast g r owing     1/ 2 () : 8 . B mm      Don oho et al.  [2] obtained  inequ ality (4)  with opt imal  (up to a con s t ant factor) B(m)=24,  but not optimal A(m):= lo g mm    and   2/ 3 1 () 20 C Temlyakov and Zheltov [1 0] proved in e quality (4)  wi th  lo g () : 2 , m Am m    B(m):= and  () , C  which g uara n tee s  ine quality  2l o g 1 2 26 m m In other wo rd s, the y  proved   . T h eorem 1 ,  For e ve ry cohe rent dictionary and any function f H D     lo g 2l o g 2 1 (, ) 3 (, ) , 2 . 26      m m m m fO M P f f i f m DD   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Lebe sg ue-t y p e  Inequalit y for Orth ogo nal  Matching Pu rsuit for  µ - coherent … (Y e Peixin 215 Re cently Eug ene Livshitz [ 6 ] prove (4)  with  1 ( ) : 2 , ( ) : 2.7, ( ) 20 Am m B m C  . I n   other word s,  he provedh ich gua ra nte e s ineq uality  2l o g 1 2 26 m m In other words, they  proved     2. T h eorem ,  For e ve ry cohe rent dictionary and any function f H D      22 (, ) 2 . 7 (, )   mm m fO M P f f f DD      f or all 1 1. 20 m       The aim of this pap er is to  prove (4) with     1 ( ) : 2 , ( ) : 2.47 ( 1 ) , 0 , ( ) , 20 Am m B m C      (5)     and thereby  improve s  ab o v e result.     . T h eorem 3   ,  For e ve ry cohe rent dictionary and any function f H D   0  , we  have     22 ( , ) 2.47 ( 1 ) ( , )   mm m ff O M P f f DD     f or all     1 1. 20 m        2. Preliminary   lemmas   By condition s of Theore m  3 , we have     1 / 20. m     (6)     We u s e several stand ard le mmas to p r ov e Theo rem 3.   Lemma 1. ,1 2 , For any n n m and      1 ,, ,  n ii i i i hc c  D      we h a v e   11 max | , | max | | ( 1 2 ) ii in in hc m   , (7)    11 ma x | , | ma x | | [ 1 ( 2 1 ) ] , ii in in hc m      (8)     Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  213 – 2 2 6   216 1 11 ma x | | m a x | , |   , ii in in cK h       (9)     whe r e      1 11 0 1 0 : 1 ( 2 1 ) 9 10 9 K m       (10 )     pro o f . For any  1 in  , using (1 ), we ha ve    1, ,, , ii i i j j i jn i j hc c         1 (1 ) ( m a x | | ) ii in cn c        1 (m a x | | )2 ii in cc m          1 (m a x | | ) ( 1 2 ) . i in cm        Then we get inequ ality (7).   Similarly    1 ,( 1 ) ( m a x | | ) ii i in hc n c        This imply inequality (8).   Inequality (9 ) follows from (8).   As a co nse q u ence of Lem ma 1, we de ri ve the followi ng lemma.          Lemma 2.  2, , , 1 .  i Le t n m h H i n D   Suppo se that   1 (, , ) 1 () . n n s pa n i i i Proj h c    Then   1 11 max | | m ax | , | . ii in i n cK h        pro o f .Set       1 (, , ) 1 () . n n s pa n i i i hP r o j h c        It is easy to see that     ,, , 1 . ii hh i n     Thus th e lem m a follows from inequ ality (9) for h For  1 n  we defin e     1 :, . nn n df g     (11 )   Let numbe r , ,1 , in xn 1 in    satisfy the equ ality    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Lebe sg ue-t y p e  Inequalit y for Orth ogo nal  Matching Pu rsuit for  µ - coherent … (Y e Peixin 217 1, 1 . n nn i n i i f fx g     (12 )     The followi ng  lemma tell us ho w the value of  , in x  depen d s  on the cohe ren c e of the d i ctiona ry.  Lemma 3.   2, : For any n m w e c a n g e t the f ollow i ng e s timates     ,1 || | | , 1 1 , in n xK d i n     (13 )     ,1 || | | . nn n n x dK d     (14 )     pro o f .By the definition of OMP     1 (, , ) :( , ) ( ) .   l l l span g g f fO M P f f P r o j f D      Then we ca n see     ,0 , 1 . li f gi l     (15 )   H e nc   1 1( , , ) 1 () n nn s p a n g g n f fP r o j f     1 1( , , ) 1 () . n nn n s p a n g g n n n f dg P r o j f d g      (16 )     Usi ng (1 ) an d  (15)  we have  for  1 :, nn n hf d g      1 |, | | , | | , | | | , 1 1 , in i n i n n hg f g d g g d i n    (1 1 ) 1 |, | | , | | , | | | | | 0 . nn n n n n n n hg f g d g g d d      Suppo se that   , ,1 , in x in  sat i sf y     11 (, , ) ( , , ) 1 , 1 () ( ) . nn n s p a n gg s p a n gg n n n i n i i Proj h P roj f d g x g       By Lemma 2     ,1 1 11 ma x | | m a x | , | | | . in i n in i n x Kh g K d       (17 )     It follows fro m  (16)  and (1 2) that  (1 6 ) ( 1 2 ) 1, 1 , 11 . nn nn n i n i n n i n i ii f dg x g f f x g       Then we get the relatio n  be tween  ,, ,1 , in in x and x i n     ,, , , ,1 1 , . in i n n n n n n x xi n x d x       This an d (1 7) complete the  proof.   The followi ng  lemma provi des a n  estim a te of  {| | } n d        Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  213 – 2 2 6   218 Lemma 4.   12 1 For a n y l n m  we have     2 || | | , nl dK d     whe r e      2 10 : e xp( 2 ) exp ( 1 / 9). 9 Km     (18 )     pro o f .  Using Lem ma 3, for  12 ln m  , we have      11 1 , 1 1 || , | | , | n nn n n i n i n i df g f x g g     11 , 1 1 |, | | , | n nn i n i n i fg x g g     1 (1 ) ,, 1 || ( | | | | ) n nn n i n i dx x    1 | | [1 (1 2 ) ] n dm K    (6) , ( 1 0 ) 21 0 | | [1 (1 ) ] 20 9 n d    10 || ( 1 ) . 9 n d      H e nc e  fo r  any ,1 2 1 nl n m  , we can get     2 2 10 2 10 10 9 | | || ( 1 ) | | ( 1 ) || ( 2 ) | | . 92 9 nl m nl l l l m dd d d e x p m K d m          3.  Nota tions   By the definition of the best   m -term ap prox imation there exist  ,0 , j a   , j D   1,  jm  and  0 H  su ch t h at     0, 0 0 0 1 ,, 0 , 1 ,  m jj j j f fa j m    0 (1 ) ( , ) (1 ) ( ) , 0 .   mm ff   ‖‖ D    (19 )     Set   1 : ( , , ), (.) : (.), (.) : (.),   mL L L L L s pan P P roj P Proj    :( ) , 0 2 .  nL n Pf n m     Let the numb e , ,0 , 1 ,  jn an j m  satisfy equalities      Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Lebe sg ue-t y p e  Inequalit y for Orth ogo nal  Matching Pu rsuit for  µ - coherent … (Y e Peixin 219 , 1 :( ) ( ) .  m nL n L n j n j n j fP f P f a    (20 )     Define     11 2 1 : { { 1 ,, 2 } : { } } , : { 1 ,, 2 } \ .  m ij j Ti m g T m T     Then, for  1 n , we let    2 2 22 :{ 1 , , } , : .  n n nT TT n D d    (21 )       4. Main lemmas  Lemma 5.   2 12 , , .  Le t i n m i n T  T hen we have     19 |( ) , | . 18  Ln i Pg g   pro o f .Let  1 () . m Ln j j j Pg c   Since  2 nT  and    ,| , | , 1 ,  nj n j gg j m      it follows  from Lemma 2 that    1 1 ma x | | .  j jm cK     Therefore, we have     | ( ) , | | ( ) ,| | , | | ( ) ,|   L ni n L ni n i L n i Pg g g P g g g g P g g   11 1 |, | ( m a x | | ) ( m a x | , | )    n jj i j j i jm jm i cg c g    1 19 () . 18  mK                                                                                   Lemma 6.  1 ; Le t n T  then we h a ve     22 1 0.20 .  nn D  ‖‖     pro o f . Let    2 :. n n tT #    (22 )     If  2  n T , then  10 nn   and no prove i s  nee ded, so  we ca n assume that  1 n t . B y   Lemma 4    Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  213 – 2 2 6   220 2 2 || m i n | | . n ni iT dK d    (23 )     On the othe r hand, by defi n ition (21 )  an d (22 ) , we ha ve    2 2 2 22 2 (m i n | | ) ,   n n in i i iT iT iT dt d d D     so we get     2 1/ 2 mi n | | ( ) . n i iT n D d t      Combi n ing thi s  with (23), we obtain     1/ 2 2 || ( ) , n n D dK t   22 2 . nn dt K D    (24 )     Define     1 1 22 ,, :.    nn nT in i i n i iT i T hx g x g    (25 )     Acco rdi ng to the definition  of  n , we have  1, 1 () ( )   n nL n L n i n i i Pf P f x g 2 1, 1 () ( ) .    n Ln i n i n L iT Pf x g P h   So we get     22 2 2 11 1 || || || ( ) || || || 2 | , ( ) | || ( ) ||    nn L n n L L Ph Ph Ph    22 11 2| , | | | | | .    nn hh     (26 )     Thus to p r ov e the lem m a,  we m u st e s t i mate  1 |, | n h  and  2 || || h . Usi ng  (15 )  a nd (25),  we   obtain   (1 5 ) 1 1 ,1 ,1 11 |, | | , | | , |     mm nn j n j j n j jj h f ah ah    1 2 (2 5 ) ,1 , 1 |, |     n m jn j i n i j iT ax g   1 2 ,1 , 1 || | , | .   n m jn i n j i j iT ax g    (27 )   For any 1  lm , we have    (2 0 ) ,1 , 1 1 1 11 |, | | , | | , | | | .     mm jn j l j n j n l n l n jj aa f d      Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       Lebe sg ue-t y p e  Inequalit y for Orth ogo nal  Matching Pu rsuit for  µ - coherent … (Y e Peixin 221 By Lemma 1, we get     ,1 1 , 1 1 11 1 max | | ( max | , | | | .    m jn jn j l n im l m j aK a K d     (28 )     Then we obta i n the estimat e      ,1 1 1 || | | . m jn n j am K d      It follows  from (1) and Lemma 3 that for 1 jm   1 1 2 2 (1 3 ) ( 2 2 ) 12 ,2 , 2 1 1 |, | # m a x | | # | | | | .  n n nn in j i in n n n iT iT x gT x T K d K d t       Thus,  we can  continu e  (27 )  as      1 2 22 2 1, 1 , 1 1 |, | | | | , |    n m nj n i n j i n n j iT ha x g m K d t     22 2 2 2 2 12 12 2 5 81  m KKD m K KD KD      By condition (6), we  can  su ppo se that 01 / 4 0 , s o     1 10 1 1 . 9 91 0 3 7 1 10  K    (29 )     Acco rdi ng to Lemma 3, we  can write     1 1 2 2 22 2 1 1 2 ,, 2 2 || | | # # (m a x ) [ ( ) ]   n n nn in i i n iT iT hx g x T T ‖‖   22 2 1 1 2 12 2 # [) ] # (   nn n Kd T T   22 2 2 22 2 11 2 () ( 1 2 )  nn n K dt t K K D m    22 2 11 2 2 2 10 1 1 1 () ( 1 2 ) 1 . 1 . 9 3 7 333  KK K m D K D K D     (30 )     No w usi ng th e estimate s for  1 |, |  n h  and 2 || || h , we can co ntinue i nequ ality (26):    22 2 11 || || || || 2 | , | | | ||   nn n hh     22 2 12 2 51 1 || | | 2 81 333  n K DK D     2 1 || || 0.2 0 .  n D     This  es timate c o mpletes  the proof of the lemma.  No w we p r o c eed to the est i mate of  || || n  for  2 . nT     Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  213 – 2 2 6   222 Lemma 7 . 2 ; Le t n T  then we h a ve     22 2 1 0.76 .  nn n d  ‖‖     pro o f . Just as in th e proof of Le mma 6, we u s e the elem e n   1 2 , :. n in i iT hx g      Set     1, :( ) .  nL n n n n Pf x g      Then we ca n write     1, 1 () ( )   n nL n L n i n i i Pf P f x g   1 1, , 1 () ( )   n Ln n n n L i n i i Pf x g P x g   1 2 , () ( ) ,     n nL i n i n L iT Px g P h    22 2 2 2 || || || || 2 , ( ) || ( ) | | || || 2 | , | || | | .    nn n L L n n Ph Ph h h   (31 )     Therefore, to   prove th e le mma it suffices to  obtain  uppe r b oun d s  for 22 | | | | ,| , | ,| | | |   nn hh  . To   es timate  2 || || , h  we can u s e in eq uality (31) fro m  Lemma 6      22 2 2 1 1 2 12 2 || || [ ( #) ] #   nn n hK d T T   22 2 2 2 11 1 [2 (2 ) ] ( ) 2 ( 1 2 )  nn K dm m K K m m d    22 2 10 1 1 11 1 . 1 0 .0 04 . 9 1 0 3 7 3330  nn n dd d    (32 )     Then we proceed to the est i mate of  2 || || n Usi ng (2 0), (2 8) and the in clusio 2 nT , we ca n write   11 , 1 1 |, | | , |   m nn n n j n j n n j gd f a gd    1, 1 , 1 11 |, , | | , |      mm nn j n j n n j n j n jj f ga g d a g    ,1 1 11 (m a x | | ) m a x | , | | | .   jn j n n jm j m am g K d m    (33 )     Then u s ing L e mma 3 an d (29 ) ,(6 ) , we o b tain the esti mate    ,1 , 1 2, 2 [ ( ) ] [ ( , ) ]    nn n n n n n n n n n n x gd x d d g d                                    11 2 ( || || ) ( || || )  nn n n dK d d K d m   Evaluation Warning : The document was created with Spire.PDF for Python.