metoda Kaczmarza

Metoda Kaczmarza lub algorytm Kaczmarza to iteracyjny algorytm rozwiązywania układów równań liniowych ${\ displaystyle Ax = b}$ . Została po raz pierwszy odkryta przez polskiego matematyka Stefana Kaczmarza i została ponownie odkryta w dziedzinie rekonstrukcji obrazu z projekcji przez Richarda Gordona , Roberta Bendera i Gabora Hermana w 1970 roku, gdzie nazywa się ją techniką rekonstrukcji algebraicznej (SZTUKA). ART obejmuje ograniczenie pozytywności, czyniąc je nieliniowym.

Metodę Kaczmarza można zastosować do dowolnego liniowego układu równań, ale jej przewaga obliczeniowa w stosunku do innych metod polega na tym, że układ jest rzadki . Wykazano, że w niektórych zastosowaniach obrazowania biomedycznego jest lepsza od innych metod, takich jak filtrowanej projekcji wstecznej .

Ma wiele zastosowań, od tomografii komputerowej (CT) po przetwarzanie sygnałów . Można to również uzyskać stosując do hiperpłaszczyzn opisanych układem liniowym metodę kolejnych rzutów na zbiory wypukłe (POCS).

Algorytm 1: Algorytm Kaczmarza

Niech $będzie$ układem równań liniowych , niech będzie liczbą wierszy ZA , za { \ $i$$}}$ { $i}$$Displaystyle$ m th wiersz macierzy o wartościach $zespolonych$ i niech będzie dowolnym początkowym przybliżeniem o wartościach $Displaystyle A}$ do rozwiązania \ ${\ Displaystyle Ax = b}$ . ${\ Displaystyle k = 0,1, \ ldots}$ obliczyć :

${\ Displaystyle x ^ {k + 1} = x ^ {k} + {\ Frac {b_ {i }-\langle a_{i},x^{k}\rangle }{\|a_{i}\|^{2}}}{\overline {a_{i}}}}$

 

 

 

 

()

gdzie $\ Displaystyle i = k {\ bmod {m}}, i = 1,2, \ ldots m}$${\ Displaystyle {\ overline { a_ {i}}}}$ i za oznacza złożoną koniugację za ${\ displaystyle a_ {i}$ .

Jeśli system jest spójny, zbiega się do rozwiązania o minimalnej normie , pod warunkiem $,$ że iteracje zaczynają się od wektora

Bardziej ogólny algorytm można zdefiniować za pomocą parametru relaksacji ${\ Displaystyle \ lambda ^ {k}}$

${\ Displaystyle x ^ {k + 1} = x ^ {k} + \ lambda ^ {k }{\frac {b_{i}-\langle a_{i},x^{k}\rangle }{\|a_{i}\|^{2}}}{\overline {a_{i}}} }$

Istnieją wersje metody, które zbiegają się do uregulowanego ważonego rozwiązania najmniejszych kwadratów po zastosowaniu do układu niespójnych równań i, przynajmniej jeśli chodzi o zachowanie początkowe, przy niższym koszcie niż inne metody iteracyjne, takie jak metoda gradientu sprzężonego .

Algorytm 2: Randomizowany algorytm Kaczmarza

Thomas Strohmer i Roman Vershynin wprowadzili losową wersję metody Kaczmarza dla ${\ Displaystyle \| a_ {i} \|^ {2}.}$ układów liniowych, w której i -te równanie jest wybierane losowo z prawdopodobieństwem proporcjonalnym do

Metodę tę można postrzegać jako szczególny przypadek stochastycznego spadku gradientu .

W takich okolicznościach $zbiega$$szybko$$do$ rozwiązania zbieżności zależy tylko od skalowanego $\displaystyle \kappa (A)}$ .

Twierdzenie. Niech ${\ displaystyle x}$ będzie rozwiązaniem ${\ Displaystyle Ax = b.}$

${\ Displaystyle \ mathbb {E} \|x_ {k} -x \|^ {2} \ równoważnik \ lewo (1- \ kappa (A) ^ {-2} \ prawo) ^ {k} \ cdot \| x_{0}-x\|^{2}.}$

algorytm 2 zbiega się w ze średnim błędem: $2$

Dowód

Mamy

${\ Displaystyle \ forall z \ w \ mathbb {C} ^ {n}: \ quad \ suma _ {j = 1} ^ {m} | \ langle z, a_ {j}\rangle |^{2}\geq {\frac {\|z\|^{2}}{\|A^{-1}\|^{2}}}}$

 

 

 

 

()

Za pomocą

$\|A \|^ {2} = \ suma _ {j = 1} ^ {m} \|a_ {j} \|^$

możemy zapisać ( 2 ) jako

${\ Displaystyle \ forall z \ in \ mathbb {C} ^ {n}: \ quad \ suma _ {j = 1} ^ {m} {\ frac {\| a_ {j} \|^ {2}} \|A\|^{2}}}\left|\left\langle z,{\frac {a_{j}}{\|a_{j}\|}}\right\rangle \right|^{2 }\geq \kappa (A)^{-2}{\|z\|^{2}}}$

 

 

 

 

()

Głównym punktem dowodu jest postrzeganie lewej strony w ( 3 ) jako oczekiwanie jakiejś zmiennej losowej. Mianowicie $równania$ przypomnijmy, że przestrzeń rozwiązań jest ZA $Displaystyle Ax = b}$

${\ Displaystyle \ {y: \ langle y, a_ {j} \ rangle = b_ {j} \},$

którego normalna to ${\ Displaystyle {\ tfrac {a_ {j}} {\| a_ {j} \|^ {2}}}.}$ Zdefiniuj losowy wektor Z , którego wartości są normalnymi do wszystkich równań ${\ displaystyle Ax=b}$ , z prawdopodobieństwem jak w naszym algorytmie:

${\ Displaystyle Z = {\ Frac {a_ {j}}} {\| a_ {j} \|}}}$ z prawdopodobieństwem ${\ Displaystyle {\ Frac {\|a_ {j} \ | ^ {2}} {\| A \|^ {2}}} \ qquad \ qquad \ qquad j = 1, \ ldots, m$

Następnie ( 3 ) mówi, że

${\ Displaystyle \ forall z \ w \ mathbb {C} ^ {n}: \ quad \ mathbb {E} | \ langle z, Z \ rangle | ^ {2} \geq \kappa (A)^{-2}{\|z\|^{2}}}$

 

 

 

 

()

Rzut ${\ Displaystyle Pz = z- \ langle zx, Z \ rangle Z.}$ rozwiązań $losowego$ określony $z$

Teraz jesteśmy gotowi do analizy naszego algorytmu. Chcemy pokazać, że błąd $średnio$ na każdym kroku (uwarunkowany poprzednimi współczynnik $(A) ^ {- 2}).}$$x$ Następne przybliżenie obliczane na podstawie ${\ Displaystyle x_ {k-1}}$ jak ${\ Displaystyle x_ {k} = P_ {k} x_ {k-1},}$ gdzie ${ \displaystyle P_{1},P_{2},\ldots }$ są niezależnymi realizacjami rzutu losowego ${\ Displaystyle P.}$ Wektor jest w jądrze ${\ Displaystyle x_ {k-1} -x_ {k}}$${\ Displaystyle P_ {k}.}$ Jest ortogonalny do przestrzeni rozwiązań równania, na które projektuje się ${\ displaystyle P_ {k}}$ , który zawiera wektor ${\ displaystyle x_ {k} -x }$ (przypomnij sobie, że $.$ rozwiązaniem wszystkich równań) Wtedy ortogonalność tych dwóch wektorów daje wynik

${\ Displaystyle \|x_ {k} -x \|^ {2} = \|x_ {k-1} -x \|^ {2} - \|x_ {k-1} -x_ {k} \| ^{2}.}$

$_$ musimy _ Zgodnie $_$ definicją

${\ Displaystyle \| x_ {k-1} -x_ {k} \ | = \ langle x_ {k-1} -x ,Z_{k}\rangle }$

gdzie ${\ Displaystyle Z_ {1}, Z_ {2}, \ ldots}$ są niezależnymi realizacjami losowego wektora ${\ Displaystyle Z.}$

Zatem

${\ Displaystyle \|x_ {k} -x \|^ {2} = \ lewo (1- \ lewo | \ lewo \ langle {\ Frac {x_ {k-1} -x} {\| x_ {k- 1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.}$

$jest$ stron uzależnione od wyboru wektorów rzuty $_$ zatem ${\ Displaystyle x_ {1}, \ ldots, x_ {k-1}}$ i uśredniamy na wektorze losowym ${\ Displaystyle Z_ {k}} )$ . Następnie

${\ Displaystyle \ mathbb {E} _ {Z_ {1}, \ ldots, Z_ {k-1}} {\| x_ {k} -x \ | ^ {2}} = \ lewo (1- \ mathbb { E} _{Z_{1},\ldots,Z_{k-1},Z_{k}}\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k -1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.}$

Przez ( 4 ) i niezależność,

${\ Displaystyle \ mathbb {E} _ {Z_ {1}, \ ldots, Z_ {k-1}} {\| x_ {k} -x \ | ^ {2}} \ równoważnik (1- \ kappa (A )^{-2}){\|x_{k-1}-x\|^{2}}.}$

Biorąc pod uwagę pełne oczekiwania obu stron, dochodzimy do wniosku, że

${\ Displaystyle \ mathbb {E} \|x_ {k} -x \|^ {2} \ równoważnik (1- \ kappa (A) ^ {-2}) \ mathbb {E} {\|x_ {k -1}-x\|^{2}}.\czarnykwadrat }$

Wyższość tego wyboru została zilustrowana rekonstrukcją funkcji o ograniczonym paśmie z jej nierównomiernie rozmieszczonych wartości próbkowania. Zwrócono jednak uwagę, że sukces opisany przez Strohmera i Vershynina zależy od konkretnych wyborów, których dokonano przy tłumaczeniu podstawowego problemu, którego geometryczną naturą jest znalezienie wspólnego punktu zbioru hiperpłaszczyzn, na system algebraicznych równania. Zawsze będą istniały uzasadnione algebraiczne reprezentacje podstawowego problemu, dla których metoda selekcji będzie działać w gorszy sposób.

Iteracja Kaczmarza ( 1 ) ma interpretację czysto geometryczną: algorytm sukcesywnie rzutuje bieżącą iterację na hiperpłaszczyznę określoną przez następne równanie. Dlatego jakiekolwiek skalowanie równań jest nieistotne; można również zauważyć z ( 1 ), że każde (niezerowe) skalowanie równań jest kasowane. Tak więc w RK można użyć ${\ Displaystyle \|a_ {i}\|}$ lub wszelkie inne wagi, które mogą być istotne. W szczególności we wspomnianym przykładzie rekonstrukcji równania zostały wybrane z prawdopodobieństwem proporcjonalnym do średniej odległości każdego punktu próbkowania od jego dwóch najbliższych sąsiadów — koncepcja wprowadzona przez Feichtingera i Gröcheniga . Aby uzyskać dodatkowe postępy w tym temacie, zobacz i zawarte w nim odniesienia.

Algorytm 3: Algorytm Gowera-Richtarika

W 2015 roku Robert M. Gower i Peter Richtarik $opracowali wszechstronną$ , iteracyjną metodę rozwiązywania spójnego układu równań liniowych, przypadek szczególny. Inne przypadki specjalne obejmują losowe zejście współrzędnych, losowe zejście Gaussa i losową metodę Newtona. Wersje blokowe i wersje z ważnym próbkowaniem wszystkich tych metod również pojawiają się jako przypadki szczególne. Wykazano, że metoda cieszy się wykładniczym spadkiem szybkości (w oczekiwaniu) - znanym również jako zbieżność liniowa, w bardzo łagodnych warunkach na drodze wejścia losowości do algorytmu. Metoda Gowera-Richtarika jest pierwszym algorytmem odkrywającym związek „bliźniaczy” między tymi metodami, z których niektóre zostały niezależnie zaproponowane wcześniej, a wiele z nich było nowych.

Spostrzeżenia dotyczące Randomizowanego Kaczmarza

Ciekawe nowe spostrzeżenia na temat randomizowanej metody Kaczmarza, które można uzyskać z analizy metody, obejmują:

• Szybkość ogólna algorytmu Gowera-Richtarika dokładnie odtwarza szybkość losowej metody Kaczmarza w szczególnym przypadku, gdy została do niej zredukowana.
• Dobór prawdopodobieństw, dla których pierwotnie sformułowano i przeanalizowano losowy algorytm Kaczmarza (prawdopodobieństw proporcjonalnych do kwadratów norm rzędowych), nie jest optymalny. Optymalne prawdopodobieństwa są rozwiązaniem pewnego półokreślonego programu. Teoretyczna złożoność randomizowanego Kaczmarza z optymalnymi prawdopodobieństwami może być arbitralnie lepsza niż złożoność dla prawdopodobieństw standardowych. Jednak kwota, o którą jest lepsza, zależy od macierzy ${\ displaystyle A}$ . Istnieją problemy, dla których standardowe prawdopodobieństwa są optymalne.
• Po zastosowaniu do systemu z macierzą, $określona$ , ​​metoda Randomizowanego Kaczmarza jest równoważna metodzie Stochastic Gradient Descent (SGD) (z bardzo specjalnym stopniem) do minimalizacji silnie wypukłej funkcji kwadratowej f ( ${\ Displaystyle f (x) = {\ tfrac {1} {2}} x ^ {T} Ax-b ^ {T} x.}$ Zauważ, że ponieważ ${\ displaystyle f}$ jest wypukła, minimalizatory ${\ displaystyle f}$ musi spełniać ${\ displaystyle \ nabla f (x) = 0}$ , co jest równoważne z ${\ displaystyle Ax = b.}$ „Specjalny rozmiar kroku” to rozmiar kroku, który prowadzi do punktu, który w jednowymiarowej linii rozpiętej przez gradient stochastyczny minimalizuje odległość euklidesową od nieznanego (!) minimalizatora fa {\ $f }$ , czyli z ${\ Displaystyle x ^ {*} = A ^ {-1} b.}$ Ten wgląd uzyskano z podwójnego spojrzenia na proces iteracyjny (poniżej opisany jako „Punkt widzenia optymalizacji: ograniczenie i przybliżenie”).

Sześć równoważnych preparatów

Metoda Gowera-Richtarika ma sześć pozornie różnych, ale równoważnych sformułowań, rzucających dodatkowe światło na jej interpretację (a w konsekwencji, jak interpretować jej wiele wariantów, w tym losowego Kaczmarza):

• 1. Punkt widzenia szkicowania: Szkic i projekt
• 2. Optymalizacja punktu widzenia: ograniczenie i przybliżenie
• 3. Geometryczny punkt widzenia: przypadkowe przecięcie
• 4. Algebraiczny punkt widzenia 1: losowe rozwiązanie liniowe
• 5. Algebraiczny punkt widzenia 2: Losowa aktualizacja
• 6. Analityczny punkt widzenia: losowy punkt stały

Opiszemy teraz niektóre z tych punktów widzenia. Metoda zależy od 2 parametrów:

• dodatnio określona macierz dająca początek ważonemu euklidesowemu iloczynowi wewnętrznemu $} Przez}$$y$$x, y \ rangle _ {B}: = x ^ {$ i normę indukowaną

${\ Displaystyle \|x\|_ {B} = \ lewo (\ langle x, x \ rangle _ {B} \right)^{\frac {1}{2}},}$

• $i$ macierz losowa $prawdopodobnie$ tyloma wierszami, losową liczbą kolumn).

1. Szkic i projekt

$k , {$ iterację nowy punkt $k}}$ obliczany przez narysowanie losowej macierzy $x ^$ w postaci iid fashion z jakiejś stałej dystrybucji) i setting

${\ Displaystyle x ^ {k + 1} = {\ underset {x} {\ nazwa operatora {arg \ min}}} \ | xx ^ {k} \ | _ {B} {\ tekst {z zastrzeżeniem}} S ^ {T}Topór=S^{T}b.}$

$Oznacza$ to, $styl wyświetlania S^{T}Ax=S^{T}b}$ rzut losowo naszkicowany $system$${$ . Ideą tej metody jest wybranie $naszkicowany$ system był znacznie prostszy niż rozwiązanie oryginalnego systemu ${\ Displaystyle Ax = b}$ . Randomizowana metoda Kaczmarza $p$ uzyskiwana przez wybranie jako $macierz$$prawdopodobieństwem$${\ Displaystyle p_ {i} = \| a_ {i} \|_ {2} ^ {2}/\| A \ | _ {F} ^ {2}.} Różne$ jako jednostkowy wybory ${\ displaystyle B}$$wariantów$ prowadzą do różnych metody.

2. Ograniczenie i przybliżenie

Pozornie inne, ale całkowicie równoważne sformułowanie metody (uzyskane poprzez dualność Lagrange'a) jest

$\ Displaystyle x ^ {k + 1} = {\ underset {x }{\operatorname {arg\ min} }}\left\|xx^{*}\right\|_{B}{\text{ temat }}x=x^{k}+B^{-1} A^{T}Sy,}$

gdzie ${\ Displaystyle Ax = b.}$ może się zmieniać i $dowolnym$ systemu $b$$Stąd$ uzyskuje się najpierw ${\ Displaystyle B ^ {- 1} A ^ {T} S}$ macierzy losowej , tj. do

${\ Displaystyle \ lewo \ {h: h = B ^ {- 1} A ^ {T} Sy, \ quad y {\ tekst {może zmieniać }}\prawo\},}$

$x ^ {*}}$ wybierając punkt z tej podprzestrzeni, który najlepiej przybliża $displaystyle$ . To sformułowanie może wyglądać zaskakująco, ponieważ wydaje się niemożliwe wykonanie kroku $przybliżenia$ ze względu na fakt, że nie jest znany (w to właśnie próbujemy obliczyć!) Jednak nadal można to zrobić, po prostu dlatego, że obliczone w ten sposób jest takie samo jak $}$${\ Displaystyle x ^ {k + 1}}$$obliczone$ na podstawie szkicu i sformułowania projektu, a ponieważ pojawia się tam

5. Losowa aktualizacja

Aktualizację można również zapisać jawnie jako

${\ Displaystyle x ^ {k + 1} = x ^ { k}-B^{-1}A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\sztylet }S^{T}\left (Topór^{k}-b\prawo),}$

gdzie przez ${\ Displaystyle M ^ {\ sztylet}}$ oznaczamy pseudo-odwrotność macierzy Moore'a $Penrose'a$ . Stąd metodę $}$ zapisać w postaci , gdzie , gdzie k ${$ to losowy wektor aktualizacji .

Pozwalając $_$ _ $k} -b)} zawsze$${$ rozwiązanie i że dla wszystkich takich rozwiązań wektor ${\ Displaystyle x ^ {k + 1} -B ^ {- 1} A ^ {T} Sy ^ {k}}$ jest taki sam. Dlatego nie ma znaczenia, które z tych rozwiązań zostanie wybrane, a metodę można również zapisać jako ${\ Displaystyle x ^ {k + 1} = x ^ {k}-B^{-1}A^{T}Sy^{k}}$ . Pseudo-odwrotność prowadzi tylko do jednego konkretnego rozwiązania. Rola pseudo-odwrotności jest dwojaka:

• Pozwala na zapisanie metody w jawnej formie „losowej aktualizacji”, jak powyżej,
• Ułatwia analizę dzięki końcowemu, szóstemu sformułowaniu.

6. Losowy punkt stały

Jeśli odejmiemy od obu stron formuły losowej aktualizacji, oznaczmy ${\ Displaystyle x ^ {*}}$

${\ Displaystyle Z: = A ^ {T} S \ lewo (S ^ {T} AB ^ {- 1} A ^ {T}S\right)^{\sztylet}S^{T}A,}$

i korzystając z faktu, że dochodzimy do ostatniego sformułowania: ${\ Displaystyle Ax ^ {*} = b,}$

${\ Displaystyle x ^ {k + 1} -x ^ {*} = \ lewo (IB ^ {-1} Z\right)\left(x^{k}-x^{*}\right),}$

gdzie $.$ macierzą tożsamości Macierz $.$ losowa

Konwergencja

Przyjmując warunkowe oczekiwania w szóstym sformułowaniu (warunkowe na ), otrzymujemy ${\ displaystyle x ^ {k}}$

${\ Displaystyle \ mathbb {E} \ lewo. \ lewo [x ^ {k + 1} -x ^ {*} \ prawo | x ^ {k} \ prawo] = \ lewo (IB ^ {-1} \ mathbb {E} [Z]\prawo)\lewo[x^{k}-x^{*}\prawo].}$

Ponownie przyjmując oczekiwania i korzystając z własności wieży oczekiwań, otrzymujemy

${\ Displaystyle \ mathbb {E} \ lewo [x ^ {k + 1} -x ^ {*} \ prawo] = (IB ^ {-1} \ mathbb {E} [Z]} \ mathbb {E} \ lewo[x^{k}-x^{*}\prawo].}$

Pokazują to Gower i Richtarik

$\ Displaystyle \ rho: = \ lewo \ | IB ^ {- {\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max} \left(IB^{-1}\mathbb {E} [Z]\right),}$

gdzie norma macierzowa jest zdefiniowana przez

${\ Displaystyle \ | M \ | _ {B}: = \ max _ {x \ neq 0} {\ Frac {\| Mx \ | _ {B}} {\| x \ | _ {B}}}. }$

Co więcej, bez żadnych założeń co do $Displaystyle$ ma się $0 \ równoważnik \ rho \ równoważnik 1.}$ Przyjmując normy i rozwijając powtarzalność, otrzymujemy S {\ displaystyle S}

Twierdzenie [Gower i Richtarik 2015]

${\ Displaystyle \ lewo \|\ mathbb {E} \ lewo [x ^ {k} -x ^ {*} \ prawo] \ prawo \ | _ {B} \ równoważnik \ rho ^ {k} \ | x ^ { 0}-x^{*}\|_{B}.}$

Uwaga . Wystarczającym warunkiem, aby oczekiwane reszty zbiegały się do 0, jest $to$ osiągnąć, jeśli ma pełny rząd kolumn iw bardzo łagodnych $warunkach$${\ displaystyle S.}$ Zbieżność metody można ustalić również bez założenia pełnej rangi kolumny w inny sposób.

Możliwe jest również pokazanie silniejszego wyniku:

Twierdzenie [Gower i Richtarik 2015]

Oczekiwane kwadraty norm (zamiast norm oczekiwań) zbiegają się w tym samym tempie:

${\ Displaystyle \ mathbb {E} \ lewo \ | \ lewo [x ^ {k} -x ^ {*} \ prawo] \ prawo \ | _ {B} ^ {2} \ równoważnik \ rho ^ {k} \ lewo\|x^{0}-x^{*}\prawo\|_{B}^{2}.}$

Uwaga . Ten drugi typ zbieżności jest silniejszy ze względu na następującą tożsamość, która zachodzi dla dowolnego wektora losowego i dowolnego ustalonego wektora: $x ^ {*}}: x {\ displaystyle x$$\ displaystyle$ }

${\ Displaystyle \ lewo \|\ mathbb {E} \ lewo [xx ^ {*} \ prawo] \ prawo \ | ^ {2} = \ mathbb {E} \ lewo [\ lewo \ | xx ^ {*} \ prawo\|^{2}\prawo]-\mathbb {E} \lewo[\|x-\mathbb {E} [x]\|^{2}\prawo].}$

Konwergencja Randomizowanego Kaczmarza

Widzieliśmy, że losowa metoda Kaczmarza pojawia się jako szczególny przypadek metody Gowera-Richtarika dla ${\ displaystyle B = I}$ i ${\ displaystyle S}$ będąc ${\ displaystyle i ^ {th} }$ jednostkowy wektor współrzędnych z prawdopodobieństwem ${\ Displaystyle p_ {i} = \| a_ {i} \|_ {2} ^ {2}/\|A \|_{F}^{2},}$ gdzie ${\ displaystyle a_ {i}}$ jest wierszem ${\ Displaystyle A.}$${\ displaystyle i ^ {th}}$ Można to sprawdzić za pomocą bezpośredniego obliczenia

${\ Displaystyle \ rho = \|IB ^ {-1} \ mathbb {E} [Z] \|_ {B} = 1- {\ Frac {\ lambda _ {\ min} (A ^ {T} A) }{\|A\|_{F}^{2}}}.}$

Algorytm 4: PLSS-Kaczmarz

Ponieważ zbieżność (randomizowanej) metody Kaczmarza zależy od szybkości zbieżności, metoda może powodować powolny postęp w niektórych praktycznych problemach. Aby zapewnić skończone zakończenie metody, Johannes Brust i Michael Saunders (akademiccy) opracowali proces, który uogólnia (randomizowaną) iterację Kaczmarza i kończy się co najwyżej iteracjami do rozwiązania dla spójnego systemu ${\ Displaystyle Ax = b}$${\ displaystyle m}$ . Proces opiera się na redukcji wymiarowości , lub projekcje na niższe przestrzenie wymiarowe, stąd nazwa PLSS (Projected Linear Systems Solver). Iterację PLSS-Kaczmarz można uznać za uogólnienie

${\ Displaystyle x ^ {k + 1} = x ^ {k} + A_ {:, 1: k} ^ {T} (A_ {1: k,:} A_ {:, 1: k} ^ {T} )^{\sztylet}(b_{1:k}-A_{1:k,:}x^{k})}$

gdzie jest wybór wierszy 1 do $\ Displaystyle$ wszystkich kolumn ${1: k,:$$}$ . Randomizowana wersja metody wykorzystuje ${\ Displaystyle \ {i_ {1}, \ ldots, i_ { k-1},i_{k}\}}$ w każdej iteracji: ${$ gdzie $_$${\ Displaystyle 1,2, ..., m}$ w . Iteracja zbiega się do rozwiązania, gdy ${\ displaystyle k = m}$ . W szczególności, ponieważ utrzymuje, że $A_ {1: m,:} = A}$

${\ Displaystyle Ax ^ {m + 1} = Ax ^ {m} + AA ^ {T} (AA^{T})^{\sztylet}(b-Topór^{m})=b}$

$a$ zatem układu Obliczanie iteracji w PLSS-Kaczmarz można uprościć i efektywnie zorganizować. Otrzymany algorytm wymaga jedynie iloczynów macierzowo-wektorowych i ma postać bezpośrednią

    
    

    
        
        
        
                
        
         algorytm  PLSS-Kaczmarz  wprowadza  :  macierz  A  prawa strona  b  wyprowadza:  rozwiązanie  x  takie, że  Ax=b  x := 0  ,  P = [0]  dla  k  w  1,2,...,m  do  a  :=  A( i  k  ,:)' // Wybierz indeks i  k  w 1,...,m bez ponownego próbkowania  d  :=  P' * a  c  1  :=  norm(a)  c  2 
        
        
          :=  norma(d)  c  3  :=  (b  i  k  -x'*a)/((c  1  -c  2  )*(c  1  +c  2  ))  p  := c  3  *(a - P*( P'*a))  P  := [ P, p/norm(p) ] // Dołącz znormalizowaną aktualizację  x  := x + p  return  x 

Notatki

• 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. Serie A, Sciences Mathématiques , tom. 35, s. 355–357
• Chong, Edwin KP; Zak, Stanisław H. (2008), Wprowadzenie do optymalizacji (wyd. 3), John Wiley & Sons, s. 226–230
•   Gordon, Ryszard ; Bender, Robert; Herman, Gabor (1970), „Techniki rekonstrukcji algebraicznej (ART) dla trójwymiarowej mikroskopii elektronowej i fotografii rentgenowskiej”, Journal of Theoretical Biology , 29 (3): 471–481, Bibcode : 1970JThBi..29..471G , doi : 10.1016/0022-5193(70)90109-8 , PMID 5492997
• Gordon, Richard (2011), Zatrzymaj raka piersi teraz! Wyobrażanie sobie ścieżek obrazowania prowadzących do wyszukiwania, niszczenia, leczenia i czujnego oczekiwania na raka piersi przed przerzutami. W: Rak piersi – choroba lobarska, redaktor: Tibor Tot , Springer, s. 167–203
•   Herman, Gabor (2009), Podstawy tomografii komputerowej: Rekonstrukcja obrazu z projekcji (wyd. 2), Springer, ISBN 9781846287237
• Cenzor, Yair ; Zenius, SA (1997), Optymalizacja równoległa: teoria, algorytmy i aplikacje , Nowy Jork: Oxford University Press
• Aster, Ryszard; Borchers, Brian; Thurber, Clifford (2004), Szacowanie parametrów i problemy odwrotne , Elsevier
•   Strohmer, Tomasz; Vershynin, Roman (2009), „Losowy algorytm Kaczmarza dla systemów liniowych o zbieżności wykładniczej” (PDF) , Journal of Fourier Analysis and Applications , 15 (2): 262–278, arXiv : math / 0702226 , doi : 10.1007/s00041 -008-9030-4 , S2CID 1903919
•   Needell, Deanna; Srebro, Nati; Ward, Rachel (2015), „Stochastyczne zejście gradientowe, ważone próbkowanie i losowy algorytm Kaczmarza”, Mathematical Programming , 155 (1–2): 549–573, arXiv : 1310,5715 , doi : 10,1007/s10107-015-0864- 7 , S2CID 2370209
•    Cenzor, Yair; Herman Gabor ; Jiang, M. (2009), „Notatka o zachowaniu losowego algorytmu Kaczmarza Strohmera i Vershynina”, Journal of Fourier Analysis and Applications , 15 (4): 431–436, doi : 10.1007/s00041-009-9077 -x , PMC 2872793 , PMID 20495623
•   Strohmer, Tomasz; Vershynin, Roman (2009b), „Komentarze dotyczące randomizowanej metody Kaczmarza”, Journal of Fourier Analysis and Applications , 15 (4): 437–440, doi : 10.1007/s00041-009-9082-0 , S2CID 14806325
•   Bass, Richard F .; Gröchenig, Karlheinz (2013), „Odpowiednie próbkowanie funkcji o ograniczonym paśmie”, Illinois Journal of Mathematics , 57 (1): 43–58, arXiv : 1203,0146 , doi : 10,1215/ijm/1403534485 , S2CID 42705738
•   Gordon, Dan (2017), „Podejście derandomizacji do odzyskiwania sygnałów o ograniczonym paśmie w szerokim zakresie losowych częstotliwości próbkowania”, Algorytmy numeryczne , 77 (4): 1141–1157, doi : 10.1007 / s11075-017-0356-3 , S2CID 1794974
• Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Proceedings of the 2. International Congress on Computer Applications and Computational Science 2011 , tom. 2, Springer, s. 465–469
•   Gower, Robert; Richtarik, Peter (2015a), „Randomizowane metody iteracyjne dla systemów liniowych”, SIAM Journal on Matrix Analysis and Applications , 36 (4): 1660–1690, arXiv : 1506,03296 , doi : 10,1137/15M1025487 , S2CID 8215294
• Gower, Robert; Richtarik, Peter (2015b), „Stochastyczne podwójne wejście do rozwiązywania układów liniowych”, arXiv : 1512,06890 [ math.NA ]
• Brust, Johannes J; Saunders, Michael A (2022), „PLSS: A Projected Linear Systems Solver”, SIAM Journal on Scientific Computing , arXiv : 2207.07615

Linki zewnętrzne

• [1] Randomizowany algorytm Kaczmarza ze zbieżnością wykładniczą
• [2] Komentarze do randomizowanej metody Kaczmarza