L1-նորմ հիմնական բաղադրիչների վերլուծություն

L1-նորմ հիմնական բաղադրիչի վերլուծությունը (L1-PCA) հանդիսանում է բազմաբնույթ տվյալների վերլուծության ընդհանուր մեթոդ։ L1-PCA հաճախ ավելի նախընտրելի է ստանդարտ L2-նորմ հիմնական բաղադրիչը վերլուծությունից (PCA), երբ վերլուծած տվյալները պարունակում են հեռավոր կետեր(outliers) ։
Ինչպես L1-PCA- ն, այնպես էլ ստանդարտ PCA- ն փնտրում են ուղղահայաց ուղղություններ հիմնական բաղադրիչների համար, որոնք սահմանում են այն տեղը, որտեղ տվյալների ներկայացուցչությունը առավելագույնի հասցվում է ըստ ընտրված չափանիշի։ Ստանդարտ PCA-ն տվյալների ներկայացումը քանակականացնում է որպես L2- նորմայի տվյալների պրոյեկցիաների ագրեգատ կամ սկզբնական կետերի և նրանց պրոյեկցիաների Էվկլիդյան հեռավորության համարժեք ագրեգատ։ L1-PCA- ն օգտագործում է L1- նորմայի կետերի պրոյեկցիաները։ PCA և L1-PCA-ում հիմնական բաղադրիչների քանակը ավելի քիչ է, քան վերլուծված մատրիցի ռանգը։ Մատրիցը համընկնում է օրիգինալ կետերի միջոցով սահմանված տարածքի չափողականության հետ։ Այդ պատճառով, PCA- ն կամ L1-PCA- ն սովորաբար օգտագործվում են չափողականության իջեցման համար` տվյալների սեղմման կամ աղմուկը քչացնելու նպատակով։
Այնուամենայնիվ, ժամանակակից մեծ տվյալները հաճախ ներառում են հեռավոր կետեր(outlier)։ Ստանդարտ PCA- ն զգայուն է հեռավոր կետերի նկատմամբ։ Պատճառն այն է, որ L2-PCA-ի հիման վրա L2- նորմայի ձևավորումը քառակուսային շեշտադրում է կատարում յուրաքանչյուր կոորդինատի յուրաքանչյուր կետի մեծության վրա՝ ի վերջո գերագնահատելով ծայրամասային կետերը, ինչպիսիք են հեռավոր կետերը։ Մյուս կողմից, L1-norm-ի ձևակերպումից հետո L1-PCA- ն գծային շեշտադրում է կատարում յուրաքանչյուր կետի կոորդինատների վրա՝ արդյունավետորեն ՙՙզսպելով՚՚ հեռավոր կետերը։


== Ձևակերպում ==
Դիտարկենք ցանկացած մատրիցա՝ 
  
    
      
        
          X
        
        =
        [
        
          
            x
          
          
            1
          
        
        ,
        
          
            x
          
          
            2
          
        
        ,
        …
        ,
        
          
            x
          
          
            N
          
        
        ]
        ∈
        
          
            R
          
          
            D
            ×
            N
          
        
      
    
    {\displaystyle \mathbf {X} =[\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{N}]\in \mathbb {R} ^{D\times N}}
  , որը բաղկացած է 
  
    
      
        N
      
    
    {\displaystyle N}
   հատ 
  
    
      
        D
      
    
    {\displaystyle D}
  -չափանի կետերից։ Սահմանենք ռանգ՝ 
  
    
      
        r
        =
        r
        a
        n
        k
        (
        
          X
        
        )
      
    
    {\displaystyle r=rank(\mathbf {X} )}
  ։  
  
    
      
        K
      
    
    {\displaystyle K}
   ամբողջ թվի համար, որը 
  
    
      
        1
        ≤
        K
        <
        r
      
    
    {\displaystyle 1\leq K<r}
  , L1-PCA- ն ձևակերպումն է ՝ 

  
    
      
        K
        =
        1
      
    
    {\displaystyle K=1}
   համար, ( 1 ) պարզեցնում է L1-norm-ի հիմնական բաղադրիչը (L1-PC) 
  
    
      
        
          X
        
      
    
    {\displaystyle \mathbf {X} }
   գտնելը՝ 

 ( 1 ) - ( 2 ) բանաձևերում L1-norm 
  
    
      
        ‖
        ⋅
        
          ‖
          
            1
          
        
      
    
    {\displaystyle \|\cdot \|_{1}}
   վերադարձնում է իր արգումենտների բացարձակ արժեքների գումարը։ L2-norm 
  
    
      
        ‖
        ⋅
        
          ‖
          
            2
          
        
      
    
    {\displaystyle \|\cdot \|_{2}}
   վերադարձնում է իր արգումենտների քառակուսային արժեքների գումարը։ Եթե փոխարինենք 
  
    
      
        ‖
        ⋅
        
          ‖
          
            1
          
        
      
    
    {\displaystyle \|\cdot \|_{1}}
    ( 2 ) բանաձևում ` Frobenius / L2-նորմայով 
  
    
      
        ‖
        ⋅
        
          ‖
          
            F
          
        
      
    
    {\displaystyle \|\cdot \|_{F}}
   -ով, ապա խնդիրը դառնում է ստանդարտ PCA և այն լուծվում է 
  
    
      
        
          Q
        
      
    
    {\displaystyle \mathbf {Q} }
  մատրիցով, որ պարունակում է 
  
    
      
        K
      
    
    {\displaystyle K}
   դոմինանտ եզակի 
  
    
      
        
          X
        
      
    
    {\displaystyle \mathbf {X} }
  վեկտորներ (այսինքն, եզակի վեկտորներ, որոնք համապատասխանում են 
  
    
      
        K
      
    
    {\displaystyle K}
   առավելագույն եզակի արժեքներին)։
( 2 ) բանաձևում առավելագույնի չափումը կարելի է ընդլայնել՝ 


== Լուծում ==
Ցանկացած մատրիցայի համար՝ 
  
    
      
        
          A
        
        ∈
        
          
            R
          
          
            m
            ×
            n
          
        
      
    
    {\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}
  , որտեղ
  
    
      
        m
        ≥
        n
      
    
    {\displaystyle m\geq n}
  , սահմանել 
  
    
      
        Φ
        (
        
          A
        
        )
      
    
    {\displaystyle \Phi (\mathbf {A} )}
   որպես ամենամոտ (L2-norm իմաստով) մատրից 
  
    
      
        
          A
        
      
    
    {\displaystyle \mathbf {A} }
  , որն ունի օրթոնորմալ սյուներ։ Այսինքն՝ 

 Procrustes թեորեմն  ասում է, որ եթե 
  
    
      
        
          A
        
      
    
    {\displaystyle \mathbf {A} }
   ունի SVD 
  
    
      
        
          
            U
          
          
            m
            ×
            n
          
        
        
          
            Σ
          
          
            n
            ×
            n
          
        
        
          
            V
          
          
            n
            ×
            n
          
          
            ⊤
          
        
      
    
    {\displaystyle \mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }}
  , ապա 
  
    
      
        Φ
        (
        
          A
        
        )
        =
        
          U
        
        
          
            V
          
          
            ⊤
          
        
      
    
    {\displaystyle \Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }}
   .
Մարկոպուլոսը, Կարիստինոսը և Պադոսը  ցույց տվեցին, որ, եթե 
  
    
      
        
          
            B
          
          
            BNM
          
        
      
    
    {\displaystyle \mathbf {B} _{\text{BNM}}}
   երկուական միջուկային նորմայի առավելագույնի բարձրացման (BNM) խնդրի ճշգրիտ լուծումն է, ապա՝ 

 ապա 
 ( 2 )-ում L1-PCA- ի ճշգրիտ լուծումն է։ Միջուկային նորմ 
  
    
      
        ‖
        ⋅
        
          ‖
          
            ∗
          
        
      
    
    {\displaystyle \|\cdot \|_{*}}
    ( 2 )-ում վերադառնում է իր մատրիցային արգումենտի եզակի արժեքների ամփոփումը և կարող է հաշվարկվել ստանդարտ SVD- ի միջիններով։ Ավելին, այն պնդում է, որ հաշվի առնելով L1-PCA լուծումը, 
  
    
      
        
          
            Q
          
          
            L1
          
        
      
    
    {\displaystyle \mathbf {Q} _{\text{L1}}}
  , BNM- ի լուծումը կարելի է ստանալ հետևյալ կերպ՝ 
 որտեղ 
  
    
      
        
          sgn
        
        (
        ⋅
        )
      
    
    {\displaystyle {\text{sgn}}(\cdot )}
   վերադարձնում է իր մատրիցի արգումենտի 
  
    
      
        {
        ±
        1
        }
      
    
    {\displaystyle \{\pm 1\}}
   նշանի մատրից (ընդհանուր կորստի բացակայության դեպքում մենք կարող ենք դիտարկել, որ 
  
    
      
        
          sgn
        
        (
        0
        )
        =
        1
      
    
    {\displaystyle {\text{sgn}}(0)=1}
  ): Բացի այդ, դրանից հետևում է, որ 
  
    
      
        ‖
        
          
            X
          
          
            ⊤
          
        
        
          
            Q
          
          
            L1
          
        
        
          ‖
          
            1
          
        
        =
        ‖
        
          X
        
        
          
            B
          
          
            BNM
          
        
        
          ‖
          
            ∗
          
        
      
    
    {\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {B} _{\text{BNM}}\|_{*}}
   . BNM- ը ( 5 ) -ում կոմբինատորիկայի խնդիր է՝ կապված անտիպոդալ երկուական փոփոխականների հետ։ Հետևաբար, դրա ճշգրիտ լուծումը կարելի է գտնել բոլոր 
  
    
      
        
          2
          
            N
            K
          
        
      
    
    {\displaystyle 2^{NK}}
   էլեմենտների սպառիչ գնահատման միջոցով  
  
    
      
        
          
            O
          
        
        (
        
          2
          
            N
            K
          
        
        )
      
    
    {\displaystyle {\mathcal {O}}(2^{NK})}
   ասիմպտոտիկ արժեքով։ Հետևաբար, L1-PCA- ն նույնպես կարող է լուծվել BNM- ի միջոցով` 
  
    
      
        
          
            O
          
        
        (
        
          2
          
            N
            K
          
        
        )
      
    
    {\displaystyle {\mathcal {O}}(2^{NK})}
  -ով։ Պարզվում է, որ L1-PCA- ն հնարավոր է օպտիմալ կերպով (ճշգրիտ) լուծել` 
  
    
      
        N
      
    
    {\displaystyle N}
  -ում պոլինոմիալ բարդության դեպքում ֆիքսված 
  
    
      
        D
      
    
    {\displaystyle D}
  չափողականության համար , 
  
    
      
        
          
            O
          
        
        (
        
          N
          
            r
            K
            −
            K
            +
            1
          
        
        )
      
    
    {\displaystyle {\mathcal {O}}(N^{rK-K+1})}
   .Հատուկ դեպքում, երբ 
  
    
      
        K
        =
        1
      
    
    {\displaystyle K=1}
   (
  
    
      
        
          X
        
      
    
    {\displaystyle \mathbf {X} }
   միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը 

 Անցումը ( 5 ) -ից ( 8 ) -ին, երբ 
  
    
      
        K
        =
        1
      
    
    {\displaystyle K=1}
  , ճշմարիտ է, քանի որ 
  
    
      
        
          X
        
        
          b
        
      
    
    {\displaystyle \mathbf {X} \mathbf {b} }
  -ի  եզակի արժեքը  հավասար է 
  
    
      
        ‖
        
          X
        
        
          b
        
        
          ‖
          
            2
          
        
        =
        
          
            
              
                b
              
              
                ⊤
              
            
            
              
                X
              
              
                ⊤
              
            
            
              X
            
            
              b
            
          
        
      
    
    {\displaystyle \|\mathbf {X} \mathbf {b} \|_{2}={\sqrt {\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} }}}
  , յուրաքանչյուրի 
  
    
      
        
          b
        
      
    
    {\displaystyle \mathbf {b} }
   համար  . Հետո, եթե 
  
    
      
        
          
            b
          
          
            BNM
          
        
      
    
    {\displaystyle \mathbf {b} _{\text{BNM}}}
   BQM-ի լուծումն է ( 7 ) -ում, այն ընդունում է հետևյալ տեսքը. 
 որը 
  
    
      
        
          X
        
      
    
    {\displaystyle \mathbf {X} }
  -ի ճիշտ L1-PC- ն է, ինչպես սահմանված է ( 1 ) -ում։ Բացի այդ, 
  
    
      
        
          
            b
          
          
            BNM
          
        
        =
        
          sgn
        
        (
        
          
            X
          
          
            ⊤
          
        
        
          
            q
          
          
            L1
          
        
        )
      
    
    {\displaystyle \mathbf {b} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}})}
   և 
  
    
      
        ‖
        
          
            X
          
          
            ⊤
          
        
        
          
            q
          
          
            L1
          
        
        
          ‖
          
            1
          
        
        =
        ‖
        
          X
        
        
          
            b
          
          
            BNM
          
        
        
          ‖
          
            2
          
        
      
    
    {\displaystyle \|\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}
   .


== Ալգորիթմներ ==


=== Էքսպոնենցիալ բարդության ճիշտ լուծում ===
Ինչպես ցույց է տրված վերևում, L1-PCA-ի ճշգրիտ լուծումը կարելի է ստանալ հետևյալ երկաստիճան գործընթացով. 

 1. Լուծեք խնդիրը ( 5 )-ում` ստանալու համար 
  
    
      
        
          
            B
          
          
            BNM
          
        
      
    
    {\displaystyle \mathbf {B} _{\text{BNM}}}
   .
 2. Կիրառել SVD  
  
    
      
        
          X
        
        
          
            B
          
          
            BNM
          
        
      
    
    {\displaystyle \mathbf {X} \mathbf {B} _{\text{BNM}}}
  -ի վրա և ստանալ 
  
    
      
        
          
            Q
          
          
            L1
          
        
      
    
    {\displaystyle \mathbf {Q} _{\text{L1}}}
   .


=== Պոլինոմիալ բարդության ճշգրիտ լուծում ===
L1-PCA- ն հնարավոր է օպտիմալ կերպով լուծել 
  
    
      
        
          
            O
          
        
        (
        
          N
          
            r
            K
            −
            K
            +
            1
          
        
        )
      
    
    {\displaystyle {\mathcal {O}}(N^{rK-K+1})}
  , երբ 
  
    
      
        r
        =
        r
        a
        n
        k
        (
        
          X
        
        )
      
    
    {\displaystyle r=rank(\mathbf {X} )}
   հաստատուն է 
  
    
      
        N
      
    
    {\displaystyle N}
  -ի նկատմամբ (միշտ ճիշտ է սահմանափակ  
  
    
      
        D
      
    
    {\displaystyle D}
   չափողականության համար)։


== Կոմպլեքս տվյալներ ==
L1-PCA- ն ընդհանրացվել է նաև կոմպլեքս տվյալների մշակման համար։ Կոմպլեքս L1-PCA-ի համար 2018-ին առաջարկվել է երկու արդյունավետ ալգորիթմ։ 


== Կոդ ==
L1-PCA-ի համար MATLAB կոդը հասանելի է MathWorks- ում  և այլ պահոցներում ։


== Ծանոթագրություններ ==