Kaczmarzova metoda - Kaczmarz method
The Kaczmarzova metoda nebo Kaczmarzův algoritmus je iterační algoritmus k řešení soustavy lineárních rovnic . Poprvé to objevil polský matematik Stefan Kaczmarz,[1] a byl znovuobjeven v oblasti rekonstrukce obrazu z projekcí Richard Gordon, Robert Bender a Gabor Herman v roce 1970, kde se tomu říká Technika algebraické rekonstrukce (UMĚNÍ).[2] ART zahrnuje omezení pozitivity, takže je nelineární.[3]
Kaczmarzova metoda je použitelná pro jakýkoli lineární systém rovnic, ale její výpočetní výhoda ve srovnání s jinými metodami závisí na systému, který je řídký. Ukázalo se, že je v některých biomedicínských zobrazovacích aplikacích lepší než jiné metody, jako je filtrovaná zpětná projekce metoda.[4]
Má mnoho aplikací od počítačová tomografie (CT) do zpracování signálu. Lze jej získat také použitím metody postupných na hyperplany, popsané lineárním systémem projekce na konvexní sady (POCS).[5][6]
Algoritmus 1: Kaczmarzův algoritmus
Nechat být soustava lineárních rovnic, nechť být počet řádků A, být tř. řada komplex -hodnota matice a nechte být libovolná komplexní aproximace počáteční aproximace řešení . Pro vypočítat:
(1)
kde a označuje komplexní konjugace z .
Pokud je systém konzistentní, konverguje k minimu-norma řešení za předpokladu, že iterace začínají nulovým vektorem.
Obecnější algoritmus lze definovat pomocí a relaxace parametr
Existují verze metody, které konvergují k regularizovanému váženému řešení nejmenších čtverců, když je aplikováno na systém nekonzistentních rovnic a, alespoň pokud jde o počáteční chování, za nižší cenu než jiné iterační metody, jako je například metoda sdruženého gradientu.[7]
Algoritmus 2: Randomizovaný Kaczmarzův algoritmus
V roce 2009 byla randomizovaná verze Kaczmarzovy metody pro předurčeno lineární systémy představili Thomas Strohmer a Roman Vershynin[8] ve kterém i-tá rovnice je vybrána náhodně s pravděpodobností úměrnou
Tuto metodu lze považovat za konkrétní případ stochastický gradient.[9]
Za takových okolností konverguje exponenciálně rychle k řešení a míra konvergence závisí pouze na měřítku číslo podmínky .
- Teorém. Nechat být řešením Poté algoritmus 2 konverguje k v očekávání, s průměrnou chybou:
Důkaz
My máme
(2)
Použitím
můžeme psát (2) tak jako
(3)
Hlavním bodem důkazu je pohled na levou stranu v (3) jako očekávání nějaké náhodné proměnné. Jmenovitě si připomeňme, že prostor řešení rovnice je nadrovina
jehož normální je Definujte náhodný vektor Z jejichž hodnoty jsou normály všech rovnic , s pravděpodobnostmi jako v našem algoritmu:
- s pravděpodobností
Pak (3) říká to
(4)
Ortogonální projekce do prostoru řešení náhodné rovnice je dána
Nyní jsme připraveni analyzovat náš algoritmus. Chceme ukázat, že došlo k chybě snižuje v každém kroku v průměru (podmíněné předchozími kroky) alespoň o faktor Další aproximace se počítá z tak jako kde jsou nezávislé realizace náhodné projekce Vektor je v jádře Je kolmý k prostoru řešení rovnice, na kterou projekty, který obsahuje vektor (Odvolej to je řešením všech rovnic). Ortogonalita těchto dvou vektorů se poté získá
Abychom vyplnili důkaz, musíme se svázat zespodu. Podle definice , my máme
kde jsou nezávislé realizace náhodného vektoru
Tím pádem
Nyní předpokládáme, že obě strany budou podmíněny výběrem náhodných vektorů (proto opravíme výběr náhodných projekcí a tedy náhodné vektory a průměrujeme nad náhodným vektorem ). Pak
Podle (4) a nezávislost,
Bereme-li plné očekávání obou stran, dochází k závěru, že
Nadřazenost tohoto výběru byla ilustrována rekonstrukcí funkce s omezeným pásmem z jejích nerovnoměrně rozmístěných hodnot vzorkování. Bylo však na to poukázáno[10] že uváděný úspěch Strohmera a Vershynina závisí na konkrétních rozhodnutích, která zde byla učiněna při překladu základního problému, jehož geometrická podstata je najít společný bod sady hyperplánů, do soustavy algebraických rovnic. Vždy budou existovat legitimní algebraické reprezentace základního problému, pro který je metoda výběru použita[8] vystoupí horším způsobem.[8][10][11]
Kaczmarzova iterace (1) má čistě geometrickou interpretaci: algoritmus postupně promítá aktuální iteraci na nadrovinu definovanou další rovnicí. Proto je jakékoli měřítko rovnic irelevantní; je to také vidět z (1), které zruší jakékoli (nenulové) měřítko rovnic. V RK tedy lze použít nebo jakékoli jiné váhy, které mohou být relevantní. Konkrétně ve výše uvedeném příkladu rekonstrukce byly rovnice zvoleny s pravděpodobností úměrnou průměrné vzdálenosti každého bodu vzorku od jeho dvou nejbližších sousedů - koncept zavedený Feichtinger a Gröchenig. Další pokrok v tomto tématu najdete v části,[12][13] a odkazy v nich uvedené.
Algoritmus 3: Gower-Richtarikův algoritmus
V roce 2015 Robert M. Gower a Peter Richtarik[14] vyvinul univerzální randomizovanou iterační metodu pro řešení konzistentního systému lineárních rovnic který zahrnuje randomizovaný Kaczmarzův algoritmus jako speciální případ. Mezi další speciální případy patří randomizovaný sestup souřadnic, randomizovaný Gaussův sestup a randomizovaná Newtonova metoda. Blokové verze a verze s důležitým vzorkováním všech těchto metod také vznikají jako zvláštní případy. U této metody je prokázáno, že si užívá útlum exponenciální rychlosti (v očekávání) - známý také jako lineární konvergence, za velmi mírných podmínek při způsobu, jakým náhodnost vstupuje do algoritmu. Metoda Gower-Richtarik je prvním algoritmem, který odhaluje „sourozenecký“ vztah mezi těmito metodami, z nichž některé byly dříve nezávisle navrženy, zatímco mnohé byly nové.
Pohledy na randomizovaného Kaczmarze
Zajímavé nové poznatky o randomizované Kaczmarzově metodě, které lze získat z analýzy této metody, zahrnují:
- Obecná rychlost Gower-Richtarikova algoritmu přesně obnovuje rychlost randomizované Kaczmarzovy metody ve zvláštním případě, když se na ni snížila.
- Volba pravděpodobností, pro které byl randomizovaný Kaczmarzův algoritmus původně formulován a analyzován (pravděpodobnosti úměrné čtvercům norem řádků), není optimální. Optimální pravděpodobnosti jsou řešením určitého semidefinitního programu. Teoretická složitost randomizovaného Kaczmarze s optimálními pravděpodobnostmi může být libovolně lepší než složitost pro standardní pravděpodobnosti. Množství, o které je to lepší, však závisí na matici . Existují problémy, pro které jsou standardní pravděpodobnosti optimální.
- Při aplikaci na systém s maticí což je pozitivně definitivní, metoda Randomized Kaczmarz je ekvivalentní metodě Stochastic Gradient Descent (SGD) (s velmi speciální velikostí kroků) pro minimalizaci silně konvexní kvadratické funkce Všimněte si, že od té doby je konvexní, minimalizátory musí uspokojit , což odpovídá „Zvláštní velikost kroku“ je velikost kroku, která vede k bodu, který v jednorozměrné linii překlenuté stochastickým gradientem minimalizuje euklidovskou vzdálenost od neznámého (!) Minimalizátoru , jmenovitě od Tento pohled je získán z dvojího pohledu na iterativní proces (níže popsaný jako „Optimalizační hledisko: Omezit a přiblížit“).
Šest ekvivalentních formulací
Metoda Gower-Richtarik má šest zdánlivě odlišných, ale ekvivalentních formulací, které vrhají další světlo na to, jak ji interpretovat (a v důsledku toho, jak interpretovat její mnoho variant, včetně randomizovaného Kaczmarze):
- 1. Hledisko skicování: Skica a projekt
- 2. Optimalizační hledisko: Omezit a Přibližně
- 3. Geometrické hledisko: Náhodný průnik
- 4. Algebraické hledisko 1: Náhodné lineární řešení
- 5. Algebraické hledisko 2: Náhodná aktualizace
- 6. Analytické hledisko: Náhodný pevný bod
Nyní popíšeme některé z těchto hledisek. Metoda závisí na 2 parametrech:
- pozitivní určitá matice což vede k váženému euklidovskému vnitřnímu produktu a indukovaná norma
- a náhodnou matici s tolika řádky jako (a případně náhodný počet sloupců).
1. Skica a projekt
Vzhledem k předchozí iteraci nový bod se vypočítá nakreslením náhodné matice (způsobem iid z nějaké pevné distribuce) a nastavení
To znamená, se získá jako projekce na náhodně načrtnutý systém . Myšlenkou této metody je vybrat takovým způsobem, že projekce na načrtnutý systém je podstatně jednodušší než řešení původního systému . Randomizovaná metoda Kaczmarz se získá výběrem být maticí identity a být jednotkový vektor souřadnic s pravděpodobností Různé možnosti a vést k různým variantám metody.
2. Omezit a přiblížit
Zdánlivě odlišná, ale zcela ekvivalentní formulace metody (získaná Lagrangeovou dualitou) je
kde je také dovoleno měnit a kde je jakékoli řešení systému Proto, je získáno nejprve omezením aktualizace na lineární podprostor překlenutý sloupci náhodné matice , tj. do
a poté vyberte bod z tohoto podprostoru, který se nejlépe přibližuje . Tato formulace může vypadat překvapivě, protože se zdá nemožné provést aproximační krok vzhledem k tomu, že není známo (koneckonců to je to, o co se snažíme počítat!). Stále je to však možné, jednoduše proto, že vypočítaný tímto způsobem je stejný jako vypočteno pomocí náčrtu a formulace projektu a od té doby se tam neobjevuje.
5. Náhodná aktualizace
Aktualizace může být také napsána výslovně jako
kde by označujeme Moore-Penroseovu pseudo inverzi matice . Metodu lze tedy napsat ve formě , kde je náhodná aktualizace vektor.
Pronájem je možné ukázat, že systém vždy má řešení , a to pro všechna taková řešení vektor je stejný. Proto nezáleží na tom, které z těchto řešení je zvoleno, a metodu lze také napsat jako . Pseudoinverze vede pouze k jednomu konkrétnímu řešení. Role pseudo-inverze je dvojí:
- Umožňuje, aby byla metoda zapsána ve výslovné formě „náhodné aktualizace“, jak je uvedeno výše,
- Analýza je díky konečné, šesté formulaci jednoduchá.
6. Náhodný pevný bod
Pokud odečteme z obou stran vzorce pro náhodnou aktualizaci označte
a využij toho, že dorazíme k poslední formulaci:
kde je matice identity. Iterační matice, je náhodný, odtud název této formulace.
Konvergence
Převzetím podmíněných očekávání v 6. formulaci (podmíněno ), získáváme
Opětovným převzetím očekávání a použitím vlastnosti věží očekávání získáme
Gower a Richtarik[14] Ukaž to
kde je maticová norma definována
Navíc bez jakýchkoli předpokladů jeden má Přijetím norem a rozvinutím opakování získáme
Věta [Gower & Richtarik 2015]
Poznámka. Dostatečná podmínka pro to, aby se očekávané zbytky sblížily k 0, je Toho lze dosáhnout, pokud má celé pořadí sloupců a za velmi mírných podmínek dne Konvergence metody může být stanovena i bez předpokladu úplného předpokladu pořadí sloupců jiným způsobem.[15]
Je také možné ukázat silnější výsledek:
Věta [Gower & Richtarik 2015]
The očekávané čtvercové normy (spíše než normy očekávání) konvergují stejnou rychlostí:
Poznámka. Tento druhý typ konvergence je silnější kvůli následující identitě[14] který platí pro libovolný náhodný vektor a jakýkoli pevný vektor :
Konvergence randomizovaného Kaczmarze
Viděli jsme, že randomizovaná Kaczmarzova metoda se jeví jako zvláštní případ Gower-Richtarikovy metody pro a být jednotkový vektor souřadnic s pravděpodobností kde je řada To lze zkontrolovat přímým výpočtem
Další zvláštní případy
Poznámky
- ^ Kaczmarz (1937)
- ^ Gordon, Bender & Herman (1970)
- ^ Gordon (2011)
- ^ Herman (2009)
- ^ Cenzor a Zenios (1997)
- ^ Aster, Borchers & Thurber (2004)
- ^ Vidět Herman (2009) a odkazy v nich uvedené.
- ^ A b C Strohmer a Vershynin (2009)
- ^ Needell, Srebro & Ward (2009)
- ^ A b Cenzor, Herman a Jiang (2009)
- ^ Strohmer a Vershynin (2009b)
- ^ Bass & Gröchenig (2013)
- ^ Gordon (2017)
- ^ A b C Gower & Richtarik (2015)
- ^ Gower, Robert M .; Richtarik, Peter (2015). "Stochastický dvojitý výstup pro řešení lineárních systémů". arXiv:1512.06890 [matematika.NA ].
Reference
- Kaczmarz, Stefan (1937), „Angenäherte Auflösung von Systemen linearer Gleichungen“ (PDF), Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, 35, str. 355–357
- Chong, Edwin K. P .; Zak, Stanislaw H. (2008), Úvod do optimalizace (3. vyd.), John Wiley & Sons, str. 226–230
- Gordon, Richard; Bender, Robert; Herman, Gabor (1970), „Algebraické rekonstrukční techniky (ART) pro trojrozměrnou elektronovou mikroskopii a rentgenovou fotografii“, Journal of Theoretical Biology, 29 (3): 471–481, doi:10.1016/0022-5193(70)90109-8, PMID 5492997
- Gordon, Richard (2011), Zastavte rakovinu prsu hned teď! Představte si zobrazovací cesty k hledání, ničení, léčbě a ostražitému čekání na premetastázu rakoviny prsu. In: Rakovina prsu - Lobarova nemoc, editor: Tibor Tot, Springer, str. 167–203
- Herman, Gabor (2009), Základy počítačové tomografie: Rekonstrukce obrazu z projekce (2. vyd.), Springer
- Cenzor, Yair; Zenios, S.A. (1997), Paralelní optimalizace: teorie, algoritmy a aplikace, New York: Oxford University Press
- Aster, Richard; Borchers, Brian; Thurber, Clifford (2004), Odhad parametrů a inverzní problémy, Elsevier
- Strohmer, Thomas; Vershynin, Roman (2009), „Randomizovaný Kaczmarzův algoritmus pro lineární systémy s exponenciální konvergencí“ (PDF), Journal of Fourier Analysis and Applications, 15 (2): 262–278, doi:10.1007 / s00041-008-9030-4
- Needell, Deanna; Ward, Rachel; Srebro, Nati (2015), „Stochastic gradient sestup, vážené vzorkování a randomizovaný Kaczmarzův algoritmus“, Matematické programování, 155: 549–573, arXiv:1310.5715, doi:10.1007 / s10107-015-0864-7
- Cenzor, Yair; Herman, Gabor; Jiang, M. (2009), „Poznámka o chování randomizovaného Kaczmarzova algoritmu Strohmera a Vershynina“, Journal of Fourier Analysis and Applications, 15 (4): 431–436, doi:10.1007 / s00041-009-9077-x, PMC 2872793, PMID 20495623
- Strohmer, Thomas; Vershynin, Roman (2009b), „Komentáře k randomizované Kaczmarzově metodě“, Journal of Fourier Analysis and Applications, 15 (4): 437–440, doi:10.1007 / s00041-009-9082-0
- Bass, Richard F.; Gröchenig, Karlheinz (2013), „Relevant sampling of band-limited functions“, Illinois Journal of Mathematics, 57 (1): 43–58
- Gordon, Dan (2017), „Derandomizační přístup k obnovení signálu bez omezení pásma v širokém rozsahu náhodných vzorkovacích frekvencí“, Numerické algoritmy, doi:10.1007 / s11075-017-0356-3
- Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Sborník příspěvků z 2. mezinárodního kongresu o počítačových aplikacích a počítačových vědách z roku 2011, 2, Springer, str. 465–469
- Gower, Robert; Richtarik, Peter (2015), „Randomizované iterační metody pro lineární systémy“, SIAM Journal on Matrix Analysis and Applications, 36 (4): 1660–1690, arXiv:1506.03296, doi:10.1137 / 15M1025487
- Gower, Robert; Richtarik, Peter (2015), „Stochastický dvojitý výstup pro řešení lineárních systémů“, arXiv:1512.06890 [matematika.NA ]