L1-norm principal component analysis

L1-PCA vergeleken met PCA.Nominale gegevens (blauwe punten);Outlier (rood punt);Pc (zwarte lijn);L1-PC (rode lijn);Nominale maximale variantielijn (stippellijn).

L1-Norm Principal Component Analysis (L1-PCA) is een algemene methode voor multivariate gegevensanalyse.^[1] L1-PCA heeft vaak de voorkeur boven standaard L2-norm Hoofdcomponentanalyse (PCA) Wanneer de geanalyseerde gegevens kunnen bevatten uitbijters (Defecte waarden of corrupties).^[2][3][4]

Zowel L1-PCA als standaard PCA zoeken een verzameling van orthogonaal aanwijzingen (hoofdcomponenten) die een definiëren subruimte waarbij gegevensrepresentatie wordt gemaximaliseerd volgens het geselecteerde criterium.^[5][6][7] Standaard PCA kwantificeert gegevensrepresentatie als geaggregeerd van de L2-norm van het gegevenspunt projecties in de subruimte, of gelijkwaardig het aggregaat Euclidische afstand van de originele punten van hun subruimte-geprojecteerde representaties.L1-PCA gebruikt in plaats daarvan het aggregaat van de L1-Norm van de datapuntprojecties in de subruimte.^[8] In PCA en L1-PCA is het aantal hoofdcomponenten (pc's) lager dan het rang van de geanalyseerde matrix, die samenvalt met de dimensionaliteit van de ruimte die wordt gedefinieerd door de oorspronkelijke gegevenspunten.Daarom worden PCA of L1-PCA vaak gebruikt voor dimensionaliteitsvermindering voor het doel van gegevens denoising of compressie.Een van de voordelen van standaard PCA die hebben bijgedragen aan de hoge populariteit zijn goedkoop computationele implementatie door middel van singuliere waarden ontbinding (SVD)^[9] en statistische optimaliteit wanneer de gegevensset wordt gegenereerd door een waar multivariate normaal databron.

In moderne big data -sets omvatten gegevens echter vaak beschadigde, defecte punten, meestal aangeduid als uitbijters.^[10] Het is bekend dat standaard PCA gevoelig is voor uitbijters, zelfs wanneer ze als een kleine fractie van de verwerkte gegevens verschijnen.^[11] De reden is dat de L2-Norm-formulering van L2-PCA kwadratische nadruk legt op de omvang van elke coördinaat van elk gegevenspunt, uiteindelijk overdreven perifere punten, zoals uitbijters.Aan de andere kant legt L1-PCA na een L1-Norm-formulering lineaire nadruk op de coördinaten van elk gegevenspunt, waardoor uitbijters effectief worden beperken.^[12]

Formulering

Overweeg een Matrix ${\ displaystyle \ mathbf {x} = [\ mathbf {x} _ {1}, \ mathbf {x} _ {2}, \ ldots, \ mathbf {x} _ {n}] \ in \ mathbb {r}^{D \ maal n}}$ bestaande uit ${\ displaystyle n}$ ${\ DisplayStyle D}$-Dimensionale gegevenspunten.Definiëren ${\ displaystyle r = rank (\ mathbf {x})}$. Voor gehele getal ${\ displaystyle k}$ zoals dat ${\ DisplayStyle 1 \ leq K <r}$, L1-PCA is geformuleerd als:^[1]

${\ displayStyle {\ begin {uitgelijnd} & {\ ondertherSet {\ mathbf {q} = [\ mathbf {q} _ {1}, \ mathbf {q} _ {2}, \ ldots, \ mathbf {q} _ {q} _{K}] \ in \ mathbb {r} ^{d \ times k}} {\ max}} ~~ \ | \ mathbf {x} ^{\ top} \ mathbf {q} \ | _ _ _} \ \\ & {\ text {onderworpen aan}} ~~ \ mathbf {q} ^{\ top} \ mathbf {q} = \ mathbf {i} _ {k}. \ end {uitlijnd}}}$

(1)

Voor ${\ displaystyle k = 1}$, (1) vereenvoudigt het vinden van de L1-Norm Principal Component (L1-PC) van ${\ DisplayStyle \ Mathbf {x}}$ door

${\ displayStyle {\ begin {uitgelijnd} & {\ onder de {\ mathbf {q} \ in \ mathbb {r} ^{d \ maal 1}} {\ max}}} ~~ \ | \ mathbf {x} ^{{x} ^{{x} ^{{x} ^{\ top} \ mathbf {q} \ | _ {1} \\ & {\ text {onderworpen aan}} ~~ \ | \ mathbf {q} \ | _ {2} = 1. \ end {aligned}}}}$

(2)

In (1)-(2), L1-norm ${\ DisplayStyle \ | \ CDOT \ | _ {1}}$ Retourneert de som van de absolute vermeldingen van zijn argument en L2-norm ${\ DisplayStyle \ | \ CDOT \ | _ {2}}$ Retourneert de som van de vierkante inzendingen van zijn argument.Als men vervangt ${\ DisplayStyle \ | \ CDOT \ | _ {1}}$ in (2) Door de Frobenius/L2-norm ${\ DisplayStyle \ | \ CDOT \ | _ {f}}$, dan wordt het probleem standaard PCA en wordt het opgelost door de matrix ${\ DisplayStyle \ Mathbf {q}}$ dat bevat de ${\ displaystyle k}$ dominante enkelvoudige vectoren van ${\ DisplayStyle \ Mathbf {x}}$ (d.w.z. de enkelvoudige vectoren die overeenkomen met de ${\ displaystyle k}$ hoogst enkelvoudige waarden).

De maximalisatiestatistiek in (2) kan worden uitgebreid als

${\ displayStyle \ | \ Mathbf {x}^{\ top} \ mathbf {q} \ | _ {1} = \ sum _ {k = 1}^{k} \ sum _ {n = 1}^{n} | \ mathbf {x} _ {n}^{\ top} \ mathbf {q} _ {k} |.}$

(3)

Oplossing

Voor elke matrix ${\ DisplayStyle \ Mathbf {A} \ in \ Mathbb {r} ^{M \ Times N}}$ met ${\ displaystyle m \ geq n}$, definiëren ${\ DisplayStyle \ Phi (\ Mathbf {A})}$ als de dichtstbijzijnde (in de L2-Norm Sense) matrix tot ${\ DisplayStyle \ Mathbf {A}}$ dat heeft orthonormale kolommen.Dat wil zeggen, definiëren

${\ displayStyle {\ begin {uitgelijnd} \ phi (\ mathbf {a}) = & {\ onder {\ mathbf {q} \ in \ mathbb {r} ^{m \ times n}} {\ text {argmin}}} ~~ \ | \ Mathbf {a} -\ Mathbf {q} \ | _ {f} \\ & {\ text {onderhevig aan}} ~~ \ mathbf {q} ^{\ top} \ mathbf {q} = \ mathbf {i} _ {n}. \ end {uitgelijnd}}}$

(4)

Procrustes Stelling^[13][14] stelt dat als ${\ DisplayStyle \ Mathbf {A}}$ heeft SVD ${\ displayStyle \ Mathbf {u} _ {m \ times n} {\ boldsymbol {\ sigma}} _ {n \ times n} \ mathbf {v} _ {n \ times n}^{\ top}}$, dan${\ displaystyle \ phi (\ mathbf {a}) = \ mathbf {u} \ mathbf {v} ^{\ top}}$.

Markopoulos, Karystinos en Pados^[1] toonde dat, als ${\ DisplayStyle \ Mathbf {b} _ {\ text {bnm}}}$ is de exacte oplossing voor het probleem van de binaire nucleaire-norm maximalisatie (BNM)

${\ displayStyle {\ begin {uitgelijnd} {\ onder {\ mathbf {b} \ in \ {\ pm 1 \}^{n \ maal k}} {\ text {max}}}}} ~~ \ | \ Mathbf {\ Mathbf {X} \ Mathbf {b} \ | _ {*}^{2}, \ end {uitgelijnd}}}$

(5)

dan

${\ displayStyle {\ begin {uitgelijnd} \ mathbf {q} _ {\ text {l1}} = \ phi (\ mathbf {x} \ mathbf {b} _ {\ text {bnm}}}) \ end \ end \ end \ end \ eind}}$

(6)

is de exacte oplossing voor L1-PCA in (2). De nucleaire norm ${\ DisplayStyle \ | \ CDOT \ | _ {*}}$ in (2) Retourneert de sommatie van de enkelvoudige waarden van zijn matrixargument en kan worden berekend door middel van standaard SVD.Bovendien is het van mening dat, gezien de oplossing voor L1-PCA, ${\ DisplayStyle \ Mathbf {q} _ {\ text {l1}}}$, de oplossing voor BNM kan worden verkregen als

${\ displaystyle {\ begin {uitgelijnd} \ mathbf {b} _ {\ text {bnm}} = {\ text {sgn}} (\ mathbf {x} ^{\ top} \ mathbf {q} _ {\ text{L1}}) \ end {uitgelijnd}}}$

(7)

waar ${\ DisplayStyle {\ text {sgn}} (\ cdot)}$ Retourneert de ${\ DisplayStyle \ {\ PM 1 \}}$-Sign matrix van zijn matrixargument (zonder verlies van algemeenheid, kunnen we overwegen ${\ DisplayStyle {\ text {sgn}} (0) = 1}$).Bovendien volgt daaruit $tekst {bnm}} \ | _ {*}}$.Bnm in (5) is een combinatorisch Probleem over antipodale binaire variabelen.Daarom kan de exacte oplossing worden gevonden door een uitputtende evaluatie van iedereen ${\ DisplayStyle 2^{nk}}$ elementen van zijn haalbaarheidsset, met asymptotische kosten ${\ DisplayStyle {\ Mathcal {o}} (2^{nk})}$.Daarom kan L1-PCA ook worden opgelost, via BNM, met kosten ${\ DisplayStyle {\ Mathcal {o}} (2^{nk})}$ (Exponentieel in het product van het aantal gegevenspunten met het aantal gezochte componenten).Het blijkt dat L1-PCA optimaal (exact) kan worden opgelost met polynoomcomplexiteit in ${\ displaystyle n}$ voor vaste gegevensdimensie ${\ DisplayStyle D}$, ${\ DisplayStyle {\ Mathcal {o}} (n^{rk-k+1})}$.^[1]

Voor het speciale geval van ${\ displaystyle k = 1}$ (enkele L1-PC van ${\ DisplayStyle \ Mathbf {x}}$), BNM neemt de vorm van binaire quadratische maximalisatie (BQM) aan

$} ^{\ top} \ mathbf {x} ^{\ top} \ mathbf {x} \ mathbf {b}. \ end {uitgelijnd}}}$

(8)

De overgang van (5) tot (8) voor ${\ displaystyle k = 1}$ geldt waar, omdat de unieke enkelvoudige waarde van ${\ DisplayStyle \ Mathbf {x} \ Mathbf {b}}$ is gelijk aan ${\ DisplayStyle \ | \ Mathbf {x} \ Mathbf {b} \ | _ {2} = {\ sqrt {\ Mathbf {b} ^{\ top} \ Mathbf {x} ^{\ top} \ mathbf {x} \ mathbf {b}}}}$, voor iedere ${\ DisplayStyle \ Mathbf {b}}$. Dan, als ${\ DisplayStyle \ Mathbf {b} _ {\ text {bnm}}}$ is de oplossing voor BQM in (7), het houdt van dat

$\ mathbf {x} \ mathbf {b} _ {\ text {bnm}}} {\ | \ mathbf {x} \ mathbf {b} _ {\ text {bnm}}} \ | _ {2}}}} \ end{uitgelijnd}}}$

(9)

is de exacte l1-pc van ${\ DisplayStyle \ Mathbf {x}}$, zoals gedefinieerd in (1).Bovendien is het van mening dat ${\ DisplayStyle \ Mathbf {b} _ {\ text {bnm}} = {\ text {sgn}} (\ mathbf {x} ^{\ top} \ mathbf {q} _ {\ text {l1}}}})}}$ en $tekst {bnm}} \ | _ {2}}$.

Algoritmen

Exacte oplossing van exponentiële complexiteit

Zoals hierboven getoond, kan de exacte oplossing voor L1-PCA worden verkregen door het volgende tweestapsproces:

1. Los het probleem op in (5) verkrijgen ${\ DisplayStyle \ Mathbf {b} _ {\ text {bnm}}}$.2. Pas SVD aan op ${\ DisplayStyle \ Mathbf {x} \ Mathbf {b} _ {\ text {bnm}}}$ verkrijgen ${\ DisplayStyle \ Mathbf {q} _ {\ text {l1}}}$.

Bnm in (5) kan worden opgelost door uitputtende zoektocht over het domein van ${\ DisplayStyle \ Mathbf {b}}$ met kosten ${\ DisplayStyle {\ Mathcal {o}} (2^{nk})}$.

Exacte oplossing van polynoomcomplexiteit

Ook kan L1-PCA optimaal worden opgelost met kosten ${\ DisplayStyle {\ Mathcal {o}} (n^{rk-k+1})}$, wanneer ${\ displaystyle r = rank (\ mathbf {x})}$ is constant ten opzichte van ${\ displaystyle n}$ (altijd waar voor eindige gegevensdimensie ${\ DisplayStyle D}$).^[1][15]

Geschatte efficiënte oplossers

In 2008, Kwak^[12] stelde een iteratief algoritme voor voor de geschatte oplossing van L1-PCA voor ${\ displaystyle k = 1}$.Deze iteratieve methode werd later gegeneraliseerd ${\ DisplayStyle K> 1}$ componenten.^[16] Een andere geschatte efficiënte oplosser werd voorgesteld door McCoy en Tropp^[17] door middel van semi-definitieve programmering (SDP).Onlangs, L1-PCA (en BNM in (5)) werden efficiënt opgelost door middel van bit-flipping iteraties (L1-BF-algoritme).^[8][18]

L1-BF-algoritme

 1 functie L1bf (${\ DisplayStyle \ Mathbf {x}}$, ${\ displaystyle k}$): 2 Initialiseren ${\ displayStyle \ Mathbf {b} ^{(0)} \ in \ {\ pm 1 \} ^{n \ maal k}}$ en ${\ DisplayStyle {\ Mathcal {l}} \ \ LeftArrow \ {1,2, \ ldots, nk \}}$  3 Set ${\ DisplayStyle t \ LeftArrow 0}$ en ${\ displaystyle \ omega \ leftarrow \ | \ mathbf {x} \ mathbf {b} ^{(0)} \ | _ {*}}$  4 tot beëindiging (of ${\ displaystyle t}$ iteraties) 5 ${\ DisplayStyle \ Mathbf {b} \ leftarrow \ Mathbf {b} ^{(t)}}$, ${\ displaystyle t '\ leftarrow t}$  6 voor ${\ displaystyle x \ in {\ Mathcal {l}}}$  7 ${\ DisplayStyle K \ LeftArrow \ lCeil {\ frac {x} {n}} \ rceil}$, ${\ DisplayStyle n \ LeftArrow X-N (K-1)}$  8 ${\ displayStyle [\ Mathbf {b}] _ {n, k} \ leftarrow -[\ mathbf {b}] _ {n, k}}$  // flip bit  9 ${\ displaystyle a (n, k) \ leftarrow \ | \ mathbf {x} \ mathbf {b} \ | _ {*}}$  // berekend door SVD of sneller (zie[8]) 10 IF ${\ displaystyle a (n, k)> \ omega}$ 11 ${\ DisplayStyle \ Mathbf {b} ^{(t)} \ leftarrow \ Mathbf {b}}$, ${\ displaystyle t '\ leftarrow t+1}$ 12 ${\ DisplayStyle \ Omega \ LeftArrow a (n, k)}$ 13 einde 14 als ${\ displaystyle t '= t}$  // Er is geen bit omgedraaid 15 IF ${\ DisplayStyle {\ Mathcal {l}} = \ {1,2, \ ldots, nk \}}$ 16 Beëindiging 17 anders 18 ${\ DisplayStyle {\ Mathcal {l}} \ \ LeftArrow \ {1,2, \ ldots, nk \}}$ 

De rekenkosten van L1-BF zijn ${\ DisplayStyle {\ Mathcal {o}} (ndmin \ {n, d \}+n^{2} k^{2} (k^{2}+r))}}$.^[8]

Complexe gegevens

L1-PCA is ook gegeneraliseerd om te verwerken complex gegevens.Voor complexe L1-PCA werden in 2018 twee efficiënte algoritmen voorgesteld.^[19]

Tensor -gegevens

L1-PCA is ook uitgebreid voor de analyse van tensor Gegevens, in de vorm van L1-Tucker, de L1-Norm robuust analoog aan standaard Tucker -ontleding.^[20] Twee algoritmen voor de oplossing van L1-Tucker zijn L1-HOSVD en L1-HOOI.^[20][21][22]

Code

Matlab Code voor L1-PCA is beschikbaar bij MathWorks^[23] en andere repositories.^[18]

Referenties