Robustní analýza hlavních komponent - Robust principal component analysis

Robustní analýza hlavních komponent (RPCA) je modifikací široce používaného statistického postupu z analýza hlavních komponent (PCA), který funguje dobře s ohledem na hrubě poškozené pozorování. Pro Robust PCA existuje řada různých přístupů, včetně idealizované verze Robust PCA, která si klade za cíl obnovit matici nízkého stupně L₀ z vysoce poškozených měření M = L₀ + S.₀.^[1] Tohoto rozkladu v nízkořadých a řídkých matricích lze dosáhnout technikami, jako je metoda Principal Component Pursuit (PCP),^[1] Stabilní PCP,^[2] Kvantované PCP,^[3] Blokové PCP,^[4] a místní PCP.^[5] Poté se používají optimalizační metody, jako je Rozšířený Lagrangeův multiplikátor Metoda (ALM^[6]), Metoda střídavého směru (ADM^[7]), Rychlá střídavá minimalizace (FAM^[8]), Iterativně Reweighted Least Squares (IRLS ^[9][10][11]) nebo střídavé projekce (AP^[12][13]).

Algoritmy

Nekonvexní metoda

Nejmodernější záruka algoritmus pro robustní problém PCA (se vstupní maticí ${ displaystyle M = L + S}$) je algoritmus střídavého typu minimalizace.^[12] The výpočetní složitost je ${ displaystyle O left (mnr ^ {2} log { frac {1} { epsilon}} right)}$ kde vstup je superpozice nízké hodnosti (hodnosti ${ displaystyle r}$) a a řídká matice dimenze ${ displaystyle m krát n}$ a ${ displaystyle epsilon}$ je požadovaná přesnost získaného řešení, tj. ${ displaystyle | { widehat {L}} - L | _ {F} leq epsilon}$ kde ${ displaystyle L}$ je skutečná součást s nízkým hodnocením a ${ displaystyle { widehat {L}}}$ je odhadovaná nebo obnovená složka nízkého hodnocení. Tento algoritmus intuitivně provádí projekce rezidua na množinu matic nízkého řádu (prostřednictvím SVD operace) a řídké matice (přes vstupní tvrdé prahování) střídavým způsobem - tj. nízkořadé promítnutí rozdílu vstupní matice a řídké matice získané při dané iteraci následované řídkým promítnutím rozdílu vstupu matice a matice nízkého řádu získané v předchozím kroku a iterace těchto dvou kroků do konvergence.

Tento alternativní minimalizační algoritmus je později vylepšen o zrychlenou verzi. ^[13] Zrychlení je dosaženo použitím tečné projekce prostoru před promítnutím zbytku na sadu matic nízkého řádu. Tento trik zlepšuje výpočetní složitost ${ displaystyle O left (mnr log { frac {1} { epsilon}} right)}$ s mnohem menší konstantou vpředu, zatímco zachovává teoreticky zaručenou lineární konvergenci.

Konvexní relaxace

Tato metoda spočívá v uvolnění omezení pořadí ${ displaystyle pozice (L)}$ v optimalizačním problému do jaderná norma ${ displaystyle | L | _ {*}}$ a omezení řídkosti ${ displaystyle | S | _ {0}}$ na ${ displaystyle ell _ {1}}$-norma ${ displaystyle | S | _ {1}}$. Výsledný program lze vyřešit pomocí metod, jako je metoda Augmented Lagrange Multipliers.

Aplikace

RPCA má mnoho aplikací důležitých pro skutečný život, zvláště když studovaná data mohou být přirozeně modelována jako nízký stupeň plus řídký příspěvek. Následující příklady jsou inspirovány současnými výzvami v počítačová věda, a v závislosti na aplikacích může být předmětem zájmu buď komponenta nízkého hodnocení, nebo komponenta řídkých komponent:

Video dohled

Vzhledem k posloupnosti sledovací video rámců je často nutné identifikovat činnosti, které vyčnívají z pozadí. Pokud skládáme videorámečky jako sloupce matice M, pak nízkohodnotná složka L₀ přirozeně odpovídá stacionárnímu pozadí a řídké složce S₀ zachycuje pohybující se objekty v popředí.^[1][14]

Rozpoznávání obličejů

Obrázky konvexní, Lambertian povrch pod různým osvětlením se rozprostírá nízkodimenzionální podprostor.^[15] To je jeden z důvodů efektivity nízkodimenzionálních modelů pro data snímků. Zejména je snadné aproximovat obrazy lidské tváře pomocí nízkodimenzionálního podprostoru. Schopnost správně načíst tento podprostor je zásadní v mnoha aplikacích, jako je rozpoznávání obličejů a zarovnání. Ukázalo se, že na tento problém lze úspěšně použít RPCA, aby se obličej přesně obnovil.^[1]

Průzkumy

• Robustní PCA ^[14]
• Dynamický RPCA ^[16]
• Rozklad na nízké hodnosti a aditivní matice ^[17]
• Nízkohodnotné modely^[18]

Knihy, časopisy a workshopy

Knihy

• T. Bouwmans, N. Aybat a E. Zahzah. Příručka o robustním rozkladu nízkých a řídkých matic: Aplikace ve zpracování obrazu a videa, CRC Press, Taylor and Francis Group, květen 2016. (více informací: http://www.crcpress.com/product/isbn/9781498724623 )
• Z. Lin, H. Zhang, „Modely nízké úrovně ve vizuální analýze: teorie, algoritmy a aplikace“, Academic Press, Elsevier, červen 2017. (další informace: https://www.elsevier.com/books/low-rank-models-in-visual-analysis/lin/978-0-12-812731-5 )

Časopisy

• N. Vaswani „Y. Chi, T. Bouwmans, zvláštní vydání k„Přehodnocení PCA pro moderní datové sady: teorie, algoritmy a aplikace ”, Proceedings of the IEEE, 2018.
• T. Bouwmans, N. Vaswani, P. Rodriguez, R. Vidal, Z. Lin, zvláštní vydání k „Robustní podprostorové učení a sledování: teorie, algoritmy a aplikace ”, IEEE Journal of Selected Topics in Signal Processing, prosinec 2018.

Workshopy

• RSL-CV 2015: Workshop o robustním podprostorovém učení a počítačovém vidění ve spojení s ICCV 2015 (Další informace: http://rsl-cv2015.univ-lr.fr/workshop/ )
• RSL-CV 2017: Workshop o robustním podprostorovém učení a počítačovém vidění ve spojení s ICCV 2017 (Další informace: http://rsl-cv.univ-lr.fr/2017/ )

Session

• Zvláštní zasedání o „Online algoritmech pro statické a dynamické robustní PCA a kompresní snímání“ ve spojení s SSP 2018. (Další informace: https://ssp2018.org/ )

Zdroje a knihovny

Webové stránky

• Web pro odečítání pozadí
• Web DLAM
• Dokumentace z University of Illinois - Odkaz na archiv

Knihovny

The Knihovna LRS (vyvinutý společností Andrews Sobral ) poskytuje v MATLABu sbírku algoritmů nízkého a řídkého rozkladu. Knihovna byla navržena pro detekci pohybujících se objektů ve videích, ale lze ji použít i pro jiné úlohy počítačového vidění / strojového učení. V současné době LRSLibrary nabízí více než 100 algoritmů založených na matice a tenzor metody.

Reference

externí odkazy

• Knihovna LRS