Robust huvudkomponentanalys

₀₀₀ Robust Principal Component Analysis (RPCA) är en modifiering av den allmänt använda statistiska proceduren för huvudkomponentanalys (PCA) som fungerar bra med avseende på grovt korrupta observationer. Det finns ett antal olika tillvägagångssätt för Robust PCA, inklusive en idealiserad version av Robust PCA, som syftar till att återställa en låg-rankad matris L från mycket korrupta mätningar M = L +S . Denna nedbrytning i lågrankade och glesa matriser kan uppnås med tekniker som Principal Component Pursuit-metoden (PCP), stabil PCP, kvantiserad PCP, blockbaserad PCP och lokal PCP. Sedan används optimeringsmetoder såsom Augmented Lagrange Multiplier Method (ALM), Alternating Direction Method (ADM), Fast Alternating Minimization (FAM), Iteratively Reweighted Least Squares (IRLS) eller alternerande projektioner (AP).

Algoritmer

Icke-konvex metod

2014 års garanterade algoritm för det robusta PCA-problemet (med inmatningsmatrisen $M=L+S$ ) är en alternerande algoritm av minimeringstyp. Beräkningskomplexiteten är $O\left(mnr^{2}\log {\frac {1}{\epsilon }}\right)$ där indata är superpositionen av en låg rang (av rang $r$ ) och en gles matris med dimensionen $m\times n$ och $\epsilon$ är den önskade noggrannheten för den återvunna lösningen, dvs. , $\|{\widehat {L}}-L\|_{F}\leq \epsilon$ där $L$ är den verkliga lågrankade komponenten och ${\widehat {L}}$ är den uppskattade eller återvunna lågrankade komponenten. Intuitivt utför denna algoritm projektioner av residualet på uppsättningen lågrankade matriser (via SVD -operationen) och glesa matriser (via ingångsvis hård tröskel) på ett alternerande sätt - det vill säga lågrangprojektion av skillnaden inmatningsmatrisen och den glesa matrisen som erhålls vid en given iteration följt av gles projektion av skillnaden mellan inmatrisen och den lågrankade matrisen som erhölls i föregående steg, och iteration av de två stegen tills konvergens .

Denna alternerande projektionsalgoritm förbättras senare av en accelererad version, myntad AccAltProj. Accelerationen uppnås genom att applicera en tangentrymdprojektion innan återstoden projiceras på uppsättningen lågrankade matriser. Det här tricket förbättrar beräkningskomplexiteten till $O\left(mnr\log {\frac {1}{\epsilon }}\right)$ med en mycket mindre konstant framför medan den upprätthåller den teoretiskt garanterade linjära konvergensen.

En annan snabb version av accelererad alternerande projektionsalgoritm är IRCUR. Den använder strukturen för CUR-sönderdelning i alternerande projektionsramverk för att dramatiskt reducera beräkningskomplexiteten för RPCA till $O\ vänster(\max\{m,n\}r^{2}\log(m)\log(n)\log {\frac {1}{\epsilon }}\right)$

Konvex avslappning

Denna metod består i att slappna av rangbegränsningen $rank(L)$ i optimeringsproblemet till kärnkraftsnormen $\|L\|_{*}$ och sparsity constraint $\|S\|_{0}$ till $\ell _{1}$ -norm $\|S\|_{1}$ . Det resulterande programmet kan lösas med metoder som metoden Augmented Lagrange Multipliers.

Förstärkt metod för djupinlärning

Vissa nya verk föreslår RPCA-algoritmer med inlärningsbara/träningsparametrar. En sådan inlärningsbar/träningsbar algoritm kan utvecklas som ett djupt neuralt nätverk vars parametrar kan läras in via maskininlärningstekniker från en given datauppsättning eller problemdistribution. Den inlärda algoritmen kommer att ha överlägsen prestanda på motsvarande problemfördelning.

Ansökningar

RPCA har många viktiga tillämpningar i verkligheten, särskilt när data som studeras naturligt kan modelleras som en låg rang plus ett sparsamt bidrag. Följande exempel är inspirerade av samtida utmaningar inom datavetenskap , och beroende på tillämpningarna kan antingen den lågrankade komponenten eller den glesa komponenten vara föremål för intresse:

Videoövervakning

₀₀ Med tanke på en sekvens av övervakningsvideoramar krävs det ofta att man identifierar de aktiviteter som sticker ut från bakgrunden. Om vi staplar videobildrutorna som kolumner i en matris M, så motsvarar den lågrankade komponenten L naturligtvis den stationära bakgrunden och den glesa komponenten S fångar de rörliga objekten i förgrunden.

Ansiktsigenkänning

Bilder av en konvex, lambertiansk yta under varierande belysning spänner över ett lågdimensionellt delrum. Detta är en av anledningarna till effektiviteten hos lågdimensionella modeller för bilddata. I synnerhet är det lätt att approximera bilder av en människas ansikte genom ett lågdimensionellt underrum. För att korrekt kunna hämta detta delutrymme är avgörande i många applikationer som ansiktsigenkänning och justering. Det visar sig att RPCA kan tillämpas framgångsrikt på detta problem för att exakt återställa ansiktet.

Undersökningar

Robust PCA
Dynamisk RPCA
Nedbrytning i låg-rank plus additiv matris
Lågrankade modeller

Böcker, tidskrifter och workshops

Böcker

T. Bouwmans, N. Aybat och E. Zahzah. Handbook on Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing , CRC Press, Taylor and Francis Group, maj 2016. (mer information: http://www.crcpress.com/product/isbn/9781498724623 )
Z. Lin, H. Zhang, "Low-Rank Models in Visual Analysis: Theories, Algorithms, and Applications", Academic Press, Elsevier, juni 2017. (mer information: https://www.elsevier.com/books/low -rank-models-in-visual-analysis/lin/978-0-12-812731-5 )

Tidskrifter

N. Vaswani , Y. Chi, T. Bouwmans, Special Issue on “ Rethinking PCA for Modern Dataset: Theory, Algorithms, and Applications ”, Proceedings of the IEEE, 2018.
T. Bouwmans, N. Vaswani , P. Rodriguez, R. Vidal, Z. Lin, Special Issue on “ Robust Subspace Learning and Tracking: Theory, Algorithms, and Applications ”, IEEE Journal of Selected Topics in Signal Processing, december 2018.

Workshops

RSL-CV 2015: Workshop om Robust Subspace Learning och Computer Vision i samband med ICCV 2015 (För mer information: http://rsl-cv2015.univ-lr.fr/workshop/ )
RSL-CV 2017: Workshop om Robust Subspace Learning och Computer Vision i samband med ICCV 2017 (För mer information: http://rsl-cv.univ-lr.fr/2017/ )
RSL-CV 2021: Workshop om Robust Subspace Learning och Computer Vision i samband med ICCV 2021 (För mer information: https://rsl-cv.univ-lr.fr/2021/ )

Sessioner

Specialsession om "Online Algorithms for Static and Dynamic Robust PCA and Compressive Sensing" i samband med SSP 2018. (Mer information: https://ssp2018.org/ )

Resurser och bibliotek

Webbplatser

Bibliotek

LRS -biblioteket (utvecklat av Andrews Sobral ) tillhandahåller en samling lågrankade och glesa nedbrytningsalgoritmer i MATLAB. Biblioteket är designat för att detektera rörliga objekt i videor, men det kan också användas för andra datorseende/maskininlärningsuppgifter. För närvarande erbjuder LRSLibrary mer än 100 algoritmer baserade på matris- och tensormetoder .

externa länkar

LRSLibrary