miniatura|L1-PCA en comparació amb PCA. Dades nominals (punts blaus); valor atípic (punt vermell); PC (línia negra); L1-PC (línia vermella); línia de variància màxima nominal (línia de punts). L'anàlisi de components principals de la norma L1 (L1-PCA) és un mètode general per a l'anàlisi de dades multivariants. Sovint es prefereix l'anàlisi de components principals (PCA) L1 a l'anàlisi de components principals (PCA) estàndard de la norma L2 quan les dades analitzades poden contenir valors atípics (valors defectuosos o corrupcions), ja que es creu que és robusta.

Tant l'ACP-L1 com l'ACP estàndard busquen una col·lecció de direccions ortogonals (components principals) que defineixen un subespai on la representació de dades es maximitza segons el criteri seleccionat. L'ACP estàndard quantifica la representació de dades com l'agregat de la norma L2 de les projeccions de punts de dades al subespai, o equivalentment la distància euclidiana agregada dels punts originals des de les seves representacions projectades al subespai. L1-PCA utilitza en comptes d'això l'agregat de la norma L1 de les projeccions de punts de dades al subespai. En PCA i L1-PCA, el nombre de components principals (PC) és inferior al rang de la matriu analitzada, la qual cosa coincideix amb la dimensionalitat de l'espai definit pels punts de dades originals. Per tant, PCA o L1-PCA s'utilitzen habitualment per a la reducció de la dimensionalitat amb la finalitat de reduir el soroll o comprimir dades. Entre els avantatges de l'ACP estàndard que van contribuir a la seva gran popularitat hi ha la implementació computacional de baix cost mitjançant la descomposició de valors singulars (SVD) i l'optimalitat estadística quan el conjunt de dades es genera mitjançant una font de dades normal multivariant real.

Tanmateix, en els conjunts de dades massives moderns, les dades sovint inclouen punts corruptes i defectuosos, comunament anomenats valors atípics. Se sap que l'ACP estàndard és sensible als valors atípics, fins i tot quan apareixen com una petita fracció de les dades processades. El motiu és que la formulació de la norma L2 de L2-PCA posa èmfasi al quadrat en la magnitud de cada coordenada de cada punt de dades, i en última instància, sobreemfatitza els punts perifèrics, com ara els valors atípics. D'altra banda, seguint una formulació de norma L1, L1-PCA posa èmfasi lineal en les coordenades de cada punt de dades, restringint eficaçment els valors atípics.

Formulació Considereu qualsevol matriu que consisteix en punts de dades -dimensionals. Definir . Per a enter de tal manera que , L1-PCA es formula com:

(1)

Per a , () simplifica per trobar el component principal de la norma L1 (L1-PC) de per

(2)

A ( )-( ), norma L1 retorna la suma de les entrades absolutes del seu argument i la norma L2 retorna la suma de les entrades al quadrat del seu argument. Si es substitueix un a () per la norma de Frobenius /L2 , aleshores el problema esdevé un PCA estàndard i es resol mitjançant la matriu que conté el vectors singulars dominants de (és a dir, els vectors singulars que corresponen a la valors singulars més alts).

La mètrica de maximització a () es pot ampliar com a

(3)

Solució Per a qualsevol matriu amb , defineix com la matriu més propera (en el sentit de la norma L2) a que té columnes ortonormals. És a dir, definir

(4)

El teorema de Procrustes estableix que si té SVD , aleshores .

Markopoulos, Karystinos i Pados van demostrar que, si és la solució exacta al problema de maximització de normes nuclears binàries (BNM)

(5)

llavors

(6)

és la solució exacta de L1-PCA a (). La norma nuclear a () retorna la suma dels valors singulars del seu argument matricial i es pot calcular mitjançant SVD estàndard. A més, sosté que, donada la solució a L1-PCA, , la solució a BNM es pot obtenir com

(7)

on retorna el matriu de signe del seu argument matricial (sense pèrdua de generalitat, podem considerar ). A més, es dedueix que . El BNM a () és un problema combinatori sobre variables binàries antipodals. Per tant, la seva solució exacta es pot trobar mitjançant una avaluació exhaustiva de tots els elements del seu conjunt de viabilitat, amb cost asimptòtic . Per tant, L1-PCA també es pot resoldre, mitjançant BNM, amb cost (exponencial en el producte del nombre de punts de dades amb el nombre dels components buscats). Resulta que L1-PCA es pot resoldre de manera òptima (exactament) amb complexitat polinòmica en per a la dimensió de dades fixa ,

Per al cas especial de (un sol PC L1 de ), BNM pren la forma de maximització quadràtica binària (BQM)

(8)

La transició de () a () per a és cert, ja que el valor singular únic de és igual a , per a cada . Aleshores, si és la solució a BQM a (), es compleix que

(9)

és la L1-PC exacta de , tal com es defineix a (). A més, sosté que i .

Algorismes Solució exacta de la complexitat exponencial Com s'ha mostrat anteriorment, la solució exacta a L1-PCA es pot obtenir mitjançant el següent procés de dos passos:

1. Resol el problema de () per obtenir .

2. Aplica SVD a obtenir .

El BNM a () es pot resoldre mitjançant una cerca exhaustiva sobre el domini de amb cost .

Solució exacta de la complexitat polinòmica A més, L1-PCA es pot resoldre de manera òptima amb cost , quan és constant respecte a (sempre cert per a la dimensió de dades finites ).

Resolutors eficients aproximats El 2008, Kwak va proposar un algorisme iteratiu per a la solució aproximada de L1-PCA per a . Aquest mètode iteratiu es va generalitzar posteriorment per a components. Un altre solucionador eficient aproximat va ser proposat per McCoy i Tropp mitjançant programació semidefinida (SDP). Més recentment, L1-PCA (i BNM a ()) s'han resolt de manera eficient mitjançant iteracions de inversió de bits (algorisme L1-BF).

Dades complexes L1-PCA també s'ha generalitzat per processar dades complexes. Per a L1-PCA complex, es van proposar dos algorismes eficients el 2018.

Dades tensorials L1-PCA també s'ha ampliat per a l'anàlisi de dades tensorials, en forma de L1-Tucker, l'anàleg robust de la norma L1 de la descomposició estàndard de Tucker. Dos algorismes per a la solució de L1-Tucker són L1-HOSVD i L1-HOOI.

Referències

Categoria:Anàlisi matemàtica Categoria:Dades