iteracja Landwebera

Iteracja Landwebera lub algorytm Landwebera jest algorytmem do rozwiązywania źle postawionych liniowych problemów odwrotnych i został rozszerzony o rozwiązywanie problemów nieliniowych, które obejmują ograniczenia. Metoda została po raz pierwszy zaproponowana w latach pięćdziesiątych XX wieku przez Louisa Landwebera i obecnie można ją postrzegać jako szczególny przypadek wielu innych, bardziej ogólnych metod.

Podstawowy algorytm

Oryginalny algorytm Landwebera próbuje odzyskać sygnał x z (zaszumionych) pomiarów y . Wersja $,$ dla operatora liniowego A Gdy problem ma skończone wymiary , A jest tylko macierzą.

Kiedy A nie jest liczbą pojedynczą , to jawnym rozwiązaniem jest ${\ displaystyle x = A ^ {-1} y}$ . Jeśli jednak A jest źle uwarunkowane , jawne rozwiązanie jest złym wyborem, ponieważ jest wrażliwe na wszelkie szumy w danych y . Jeśli A jest liczbą pojedynczą , to jawne rozwiązanie nawet nie istnieje. Algorytm Landwebera jest próbą uregulowania problemu i jest jedną z alternatyw Regularyzacja Tichonowa . Algorytm Landwebera możemy postrzegać jako rozwiązanie:

{\ Displaystyle \ min _ {x} \| Ax-y \ | _ {2} ^ {2}/2}

przy użyciu metody iteracyjnej. Algorytm jest podany przez aktualizację

{\ Displaystyle x_ {k + 1} = x_ {k} - \ omega A ^ {*} (Ax_ {k} -y).}

gdzie współczynnik relaksacji spełnia ${\ Displaystyle 0 <\ omega <2/\ sigma _ {1} ^$ ${2}$ . Tutaj jest największą pojedynczą wartością σ $\ sigma _ {1}}$ $displaystyle$ . Jeśli zapiszemy ${\ Displaystyle f (x) = \| Ax-y \|_ {2} ^ {2}/2}$ , wtedy aktualizację można zapisać w kategoriach gradientu

{\ Displaystyle x_ {k + 1} = x_ {k} - \ omega \ nabla f (x_ {k})}

stąd algorytm jest szczególnym przypadkiem opadania gradientu .

W przypadku źle postawionych problemów metodę iteracyjną należy zatrzymać na odpowiednim indeksie iteracji, ponieważ jest ona częściowo zbieżna. Oznacza to, że iteracje zbliżają się do uregulowanego rozwiązania podczas pierwszych iteracji, ale stają się niestabilne w kolejnych iteracjach. Odwrotność indeksu iteracji $jako$ regularyzacji Odpowiedni parametr zostanie znaleziony, gdy niezgodność ${\ Displaystyle \| Ax_ {k} -y \|_ {2} ^ {2}}$ zbliża się do poziomu hałasu.

Wykorzystanie iteracji Landwebera jako algorytmu regularyzacji zostało omówione w literaturze.

Rozszerzenie nieliniowe

Ogólnie rzecz biorąc, aktualizacje generowane przez ${\ Displaystyle x_ {k + 1} = x_ {k} - \ tau \ nabla f (x_ {k})$ } wygeneruj sekwencję $,$ która zbiega się do minimalizatora f f a wielkość kroku ${\ displaystyle \ tau$ } jest wybrany tak, że ${\ Displaystyle 0 <\ tau <2/(\|\ nabla f \|^ {2})}$ gdzie ${\ Displaystyle \|\ cdot \|}$ jest normą widmową .

Ponieważ jest to specjalny rodzaj spadku gradientu, obecnie nie ma zbyt wielu korzyści z analizowania go samodzielnie jako nieliniowego Landwebera, ale taka analiza była przeprowadzana historycznie przez wiele społeczności nieświadomych ujednolicających ram.

Nieliniowy problem Landwebera był badany w wielu artykułach w wielu społecznościach; patrz np.

Rozszerzenie do problemów z ograniczeniami

Jeśli f jest funkcją wypukłą , a C jest zbiorem wypukłym , to problem

{\ Displaystyle \ min _ {x \ w C} f (x)}

można rozwiązać za pomocą ograniczonej, nieliniowej iteracji Landwebera, określonej wzorem:

{\ Displaystyle x_ {k + 1} = {\ mathcal {P}} _ {C} (x_ {k} - \ tau \ nabla f(x_{k}))}

gdzie $_$ rzutem na zbiór C . Zbieżność jest gwarantowana, gdy ${\ Displaystyle 0 <\ tau <2/(\|A\|^{2})$ } Jest to ponownie szczególny przypadek rzutowanego spadku gradientu (który jest szczególnym przypadkiem algorytmu do przodu i do tyłu), jak omówiono w.

Aplikacje

Ponieważ metoda ta istnieje od lat pięćdziesiątych XX wieku, została przyjęta i ponownie odkryta przez wiele środowisk naukowych, zwłaszcza tych badających źle postawione problemy. W rentgenowskiej tomografii komputerowej nazywa się to SIRT - technika symultanicznej rekonstrukcji iteracyjnej. Był również używany w społeczności zajmującej się wizją komputerową i przywracaniem sygnału. Jest również używany w przetwarzaniu obrazu , ponieważ wiele problemów z obrazem, takich jak dekonwolucja , jest źle postawionych. Warianty tej metody były również stosowane w problemach z rzadkimi aproksymacjami i ustawieniami wykrywania .

^ ^a ^b Landweber, L. (1951): Formuła iteracji dla równań całkowych Fredholma pierwszego rodzaju. Amer. J. Matematyka. 73, 615–624
^ ^ab ^PL Combettes i J.-C. Pesquet, „Metody podziału proksymalnego w przetwarzaniu sygnałów”, w: Algorytmy punktu stałego dla problemów odwrotnych w nauce i inżynierii (HH Bauschke, RS Burachik , PL Combettes, V. Elser, DR Luke i H. Wolkowicz, redaktorzy), s. 185–212. Springer, Nowy Jork, 2011. ArXiv
^ Louis, AK (1989): Inverse und schlecht gestellte Probleme. Stuttgart, Teubner
^ Vainikko, GM, Veretennikov, AY (1986): Procedury iteracyjne w źle postawionych problemach. Moskwa, Nauka (po rosyjsku)
^ Analiza zbieżności iteracji Landwebera dla nieliniowych źle postawionych problemów Martin Hanke, Andreas Neubauer i Otmar Scherzer. NUMERISCHE MATEMATYKA Tom 72, Numer 1 (1995), 21-37, doi : 10.1007/s002110050158
^ Eicke, B .: Metody iteracji dla wypukłych, źle postawionych problemów z ograniczeniami w przestrzeni Hilberta. liczba. Funkcja Analny. optymalnie. 13, 413–429 (1992)
^ Johansson, B., Elfving, T., Kozlovc, V., Censor, Y., Forssen, PE, Granlund, G.; „Zastosowanie metody Landwebera rzutowanej ukośnie do modelu uczenia nadzorowanego”, Math. Oblicz. Modelowanie, tom 43, strony 892–909 (2006)
^ Trussell, HJ, Civanlar, MR: Iteracja Landwebera i rzutowanie na zbiory wypukłe. IEEE Trans. Akus., Mowa, Przetwarzanie sygnału. 33, 1632-1634 (1985)
^ Anastasios Kyrillidis i Volkan Cevher (2011). „Przepisy na twarde metody progowania” . Przepisy na twarde metody progowania . s. 353–356. doi : 10.1109/CAMSAP.2011.6136024 . ISBN 978-1-4577-2105-2 . S2CID 14996037 .

[Landweber-1] Landweber, L. (1951): Formuła iteracji dla równań całkowych Fredholma pierwszego rodzaju. Amer. J. Matematyka. 73, 615–624

[Combettes-2] PL Combettes i J.-C. Pesquet, „Metody podziału proksymalnego w przetwarzaniu sygnałów”, w: Algorytmy punktu stałego dla problemów odwrotnych w nauce i inżynierii (HH Bauschke, RS Burachik , PL Combettes, V. Elser, DR Luke i H. Wolkowicz, redaktorzy), s. 185–212. Springer, Nowy Jork, 2011. ArXiv

[3] Louis, AK (1989): Inverse und schlecht gestellte Probleme. Stuttgart, Teubner

[4] Vainikko, GM, Veretennikov, AY (1986): Procedury iteracyjne w źle postawionych problemach. Moskwa, Nauka (po rosyjsku)

[5] Analiza zbieżności iteracji Landwebera dla nieliniowych źle postawionych problemów Martin Hanke, Andreas Neubauer i Otmar Scherzer. NUMERISCHE MATEMATYKA Tom 72, Numer 1 (1995), 21-37, doi : 10.1007/s002110050158

[6] Eicke, B .: Metody iteracji dla wypukłych, źle postawionych problemów z ograniczeniami w przestrzeni Hilberta. liczba. Funkcja Analny. optymalnie. 13, 413–429 (1992)

[7] Johansson, B., Elfving, T., Kozlovc, V., Censor, Y., Forssen, PE, Granlund, G.; „Zastosowanie metody Landwebera rzutowanej ukośnie do modelu uczenia nadzorowanego”, Math. Oblicz. Modelowanie, tom 43, strony 892–909 (2006)

[8] Trussell, HJ, Civanlar, MR: Iteracja Landwebera i rzutowanie na zbiory wypukłe. IEEE Trans. Akus., Mowa, Przetwarzanie sygnału. 33, 1632-1634 (1985)

[9] Anastasios Kyrillidis i Volkan Cevher (2011). „Przepisy na twarde metody progowania” . Przepisy na twarde metody progowania . s. 353–356. doi : 10.1109/CAMSAP.2011.6136024 . ISBN 978-1-4577-2105-2 . S2CID 14996037 .