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

աջից|մինի| L1-PCA-ի համեմատությունը PCA-ի հետ: Նոմինալ տվյալներ (կապույտ կետեր); հեռավոր կետեր (կարմիր կետ); PC (սև գիծ); L1-PC (կարմիր գիծ); նոմինալ առավելագույն վարիացիայի գիծ (կետագծեր):
**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- ն գծային շեշտադրում է կատարում յուրաքանչյուր կետի կոորդինատների վրա՝ արդյունավետորեն ՙՙզսպելով՚՚ հեռավոր կետերը։

## Ձևակերպում
Դիտարկենք ցանկացած մատրիցա՝ \mathbf X = [\mathbf x_1, \mathbf x_2, \ldots, \mathbf x_N] \in \mathbb R^{D \times N}, որը բաղկացած է N հատ D-չափանի կետերից։ Սահմանենք ռանգ՝ r=rank(\mathbf X)։  K ամբողջ թվի համար, որը 1 \leq K , L1-PCA- ն ձևակերպումն է՝ 
{\max}~~\| \mathbf X^\top \mathbf Q\|_1\\
&\text{subject to}~~ \mathbf Q^\top \mathbf Q=\mathbf I_K.
\end{align}
|}}

K=1 համար, (  ) պարզեցնում է L1-norm-ի հիմնական բաղադրիչը (L1-PC) \mathbf X գտնելը՝ {\max}~~\| \mathbf X^\top \mathbf q\|_1\\
&\text{subject to}~~ \| \mathbf q\|_2 =1.
\end{align}
|}} (  ) - (  ) բանաձևերում L1-norm \| \cdot \|_1 վերադարձնում է իր արգումենտների բացարձակ արժեքների գումարը։ L2-norm \| \cdot \|_2 վերադարձնում է իր արգումենտների քառակուսային արժեքների գումարը։ Եթե փոխարինենք \| \cdot \|_1  (  ) բանաձևում ` Frobenius / L2-նորմայով \| \cdot \|_F -ով, ապա խնդիրը դառնում է ստանդարտ PCA և այն լուծվում է \mathbf Qմատրիցով, որ պարունակում է K դոմինանտ եզակի \mathbf Xվեկտորներ (այսինքն, եզակի վեկտորներ, որոնք համապատասխանում են K առավելագույն եզակի արժեքներին)։

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

## Լուծում
Ցանկացած մատրիցայի համար՝ \mathbf A \in \mathbb R^{m \times n}, որտեղm \geq n, սահմանել \Phi(\mathbf A) որպես ամենամոտ (L2-norm իմաստով) մատրից \mathbf A, որն ունի օրթոնորմալ սյուներ։ Այսինքն՝ {\text{argmin}}~~\| \mathbf A - \mathbf Q\|_F\\
&\text{subject to}~~ \mathbf Q^\top \mathbf Q=\mathbf I_n.
\end{align}
|}} Procrustes թեորեմն ասում է, որ եթե \mathbf A ունի SVD \mathbf U_{m \times n} \boldsymbol \Sigma_{n \times n} \mathbf V_{n \times n}^\top, ապա \Phi(\mathbf A)=\mathbf U \mathbf V^\top  .

Մարկոպուլոսը, Կարիստինոսը և Պադոսը ցույց տվեցին, որ, եթե \mathbf B_{\text{BNM}} երկուական միջուկային նորմայի առավելագույնի բարձրացման (BNM) խնդրի ճշգրիտ լուծումն է, ապա՝ {\text{max}}~~\| \mathbf X \mathbf B\|_*^2,
\end{align}
|}} ապա  = \Phi(\mathbf X\mathbf B_{\text{BNM}})
\end{align}
|}} (  )-ում L1-PCA- ի ճշգրիտ լուծումն է։ Միջուկային նորմ \| \cdot \|_*  (  )-ում վերադառնում է իր մատրիցային արգումենտի եզակի արժեքների ամփոփումը և կարող է հաշվարկվել ստանդարտ SVD- ի միջիններով։ Ավելին, այն պնդում է, որ հաշվի առնելով L1-PCA լուծումը, \mathbf Q_{\text{L1}}, BNM- ի լուծումը կարելի է ստանալ հետևյալ կերպ՝  = \text{sgn}(\mathbf X^\top \mathbf Q_{\text{L1}}) 
\end{align}
|}} որտեղ \text{sgn}(\cdot) վերադարձնում է իր մատրիցի արգումենտի \{\pm 1\} նշանի մատրից (ընդհանուր կորստի բացակայության դեպքում մենք կարող ենք դիտարկել, որ \text{sgn}(0)=1): Բացի այդ, դրանից հետևում է, որ  \| \mathbf X^\top \mathbf Q_{\text{L1}}\|_1 = \| \mathbf X \mathbf B_{\text{BNM}}\|_* . BNM- ը (  ) -ում կոմբինատորիկայի խնդիր է՝ կապված անտիպոդալ երկուական փոփոխականների հետ։ Հետևաբար, դրա ճշգրիտ լուծումը կարելի է գտնել բոլոր 2^{NK} էլեմենտների սպառիչ գնահատման միջոցով  \mathcal O(2^{NK}) ասիմպտոտիկ արժեքով։ Հետևաբար, L1-PCA- ն նույնպես կարող է լուծվել BNM- ի միջոցով` \mathcal O(2^{NK})-ով։ Պարզվում է, որ L1-PCA- ն հնարավոր է օպտիմալ կերպով (ճշգրիտ) լուծել` N-ում պոլինոմիալ բարդության դեպքում ֆիքսված Dչափողականության համար *, <math>\mathcal{O}(N^{rK-K+1})</math>* .

Հատուկ դեպքում, երբ K=1 (\mathbf X միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը {\text{max}}~~ \mathbf b^\top \mathbf X^\top \mathbf X \mathbf b.
\end{align}
|}} Անցումը (  ) -ից (  ) -ին, երբ K=1, ճշմարիտ է, քանի որ \mathbf X \mathbf b-ի  եզակի արժեքը  հավասար է \| \mathbf X \mathbf b\|_2 = \sqrt{\mathbf b^\top \mathbf X^\top \mathbf X \mathbf b}, յուրաքանչյուրի \mathbf b  համար  . Հետո, եթե \mathbf b_{\text{BNM}} BQM-ի լուծումն է (  ) -ում, այն ընդունում է հետևյալ տեսքը.  = \Phi(\mathbf X \mathbf b_{\text{BNM}}) = \frac{\mathbf X \mathbf b_{\text{BNM}}}{\| \mathbf X \mathbf b_{\text{BNM}}\|_2} 
\end{align}
|}} որը \mathbf X-ի ճիշտ L1-PC- ն է, ինչպես սահմանված է (  ) -ում։ Բացի այդ, \mathbf b_{\text{BNM}} = \text{sgn}(\mathbf X^\top \mathbf q_{\text{L1}}) և  \| \mathbf X^\top \mathbf q_{\text{L1}}\|_1 = \| \mathbf X \mathbf b_{\text{BNM}}\|_2 .

## Ալգորիթմներ
### Էքսպոնենցիալ բարդության ճիշտ լուծում
Ինչպես ցույց է տրված վերևում, L1-PCA-ի ճշգրիտ լուծումը կարելի է ստանալ հետևյալ երկաստիճան գործընթացով. 
  1. Լուծեք խնդիրը (  )-ում` ստանալու համար \mathbf B_{\text{BNM}} .
  2. Կիրառել SVD  \mathbf X\mathbf B_{\text{BNM}}-ի վրա և ստանալ \mathbf Q_{\text{L1}} .

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

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

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

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

Կատեգորիա:Տվյալների վերլուծություն