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

L1-նորմ հիմնական բաղադրիչի վերլուծությունը (L1-PCA) հանդիսանում է բազմաբնույթ տվյալների վերլուծության ընդհանուր մեթոդ^[1]։ L1-PCA հաճախ ավելի նախընտրելի է ստանդարտ L2-նորմ հիմնական բաղադրիչը վերլուծությունից (PCA), երբ վերլուծած տվյալները պարունակում են հեռավոր կետեր(outliers)^[2][3][4]։

Ինչպես L1-PCA- ն, այնպես էլ ստանդարտ PCA- ն փնտրում են ուղղահայաց ուղղություններ հիմնական բաղադրիչների համար, որոնք սահմանում են այն տեղը, որտեղ տվյալների ներկայացուցչությունը առավելագույնի հասցվում է ըստ ընտրված չափանիշի^[5][6][7]։ Ստանդարտ PCA-ն տվյալների ներկայացումը քանակականացնում է որպես L2- նորմայի տվյալների պրոյեկցիաների ագրեգատ կամ սկզբնական կետերի և նրանց պրոյեկցիաների Էվկլիդյան հեռավորության համարժեք ագրեգատ։ L1-PCA- ն օգտագործում է L1- նորմայի կետերի պրոյեկցիաները^[8]։ PCA և L1-PCA-ում հիմնական բաղադրիչների քանակը ավելի քիչ է, քան վերլուծված մատրիցի ռանգը։ Մատրիցը համընկնում է օրիգինալ կետերի միջոցով սահմանված տարածքի չափողականության հետ։ Այդ պատճառով, PCA- ն կամ L1-PCA- ն սովորաբար օգտագործվում են չափողականության իջեցման համար` տվյալների սեղմման կամ աղմուկը քչացնելու նպատակով։

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

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

${\displaystyle {\begin{aligned}&{\underset {\mathbf {Q} =[\mathbf {q} _{1},\mathbf {q} _{2},\ldots ,\mathbf {q} _{K}]\in \mathbb {R} ^{D\times K}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{K}.\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&{\underset {\mathbf {q} \in \mathbb {R} ^{D\times 1}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {q} \|_{1}\\&{\text{subject to}}~~\|\mathbf {q} \|_{2}=1.\end{aligned}}}$

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

( 2 ) բանաձևում առավելագույնի չափումը կարելի է ընդլայնել՝

${\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}=\sum _{k=1}^{K}\sum _{n=1}^{N}|\mathbf {x} _{n}^{\top }\mathbf {q} _{k}|.}$

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

${\displaystyle {\begin{aligned}\Phi (\mathbf {A} )=&{\underset {\mathbf {Q} \in \mathbb {R} ^{m\times n}}{\text{argmin}}}~~\|\mathbf {A} -\mathbf {Q} \|_{F}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{n}.\end{aligned}}}$

Procrustes թեորեմն^[11][12] ասում է, որ եթե ${\displaystyle \mathbf {A} }$ ունի SVD ${\displaystyle \mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }}$, ապա ${\displaystyle \Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }}$ .

Մարկոպուլոսը, Կարիստինոսը և Պադոսը^[1] ցույց տվեցին, որ, եթե ${\displaystyle \mathbf {B} _{\text{BNM}}}$ երկուական միջուկային նորմայի առավելագույնի բարձրացման (BNM) խնդրի ճշգրիտ լուծումն է, ապա՝

${\displaystyle {\begin{aligned}{\underset {\mathbf {B} \in \{\pm 1\}^{N\times K}}{\text{max}}}~~\|\mathbf {X} \mathbf {B} \|_{*}^{2},\end{aligned}}}$

ապա

${\displaystyle {\begin{aligned}\mathbf {Q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {B} _{\text{BNM}})\end{aligned}}}$

( 2 )-ում L1-PCA- ի ճշգրիտ լուծումն է։ Միջուկային նորմ ${\displaystyle \|\cdot \|_{*}}$ ( 2 )-ում վերադառնում է իր մատրիցային արգումենտի եզակի արժեքների ամփոփումը և կարող է հաշվարկվել ստանդարտ SVD- ի միջիններով։ Ավելին, այն պնդում է, որ հաշվի առնելով L1-PCA լուծումը, ${\displaystyle \mathbf {Q} _{\text{L1}}}$, BNM- ի լուծումը կարելի է ստանալ հետևյալ կերպ՝

${\displaystyle {\begin{aligned}\mathbf {B} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}})\end{aligned}}}$

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

Հատուկ դեպքում, երբ ${\displaystyle K=1}$ (${\displaystyle \mathbf {X} }$ միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը

${\displaystyle {\begin{aligned}&{\underset {\mathbf {b} \in \{\pm 1\}^{N\times 1}}{\text{max}}}~~\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} .\end{aligned}}}$

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

${\displaystyle {\begin{aligned}\mathbf {q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {b} _{\text{BNM}})={\frac {\mathbf {X} \mathbf {b} _{\text{BNM}}}{\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}}\end{aligned}}}$

որը ${\displaystyle \mathbf {X} }$-ի ճիշտ L1-PC- ն է, ինչպես սահմանված է ( 1 ) -ում։ Բացի այդ, ${\displaystyle \mathbf {b} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}})}$ և ${\displaystyle \|\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}$ .

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

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

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

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

L1-PCA-ի համար MATLAB կոդը հասանելի է MathWorks- ում^[15] և այլ պահոցներում^[16]։