Landweber iteration

Landweber -iterationen eller Landweber-algoritmen är en algoritm för att lösa dåligt ställda linjära inversa problem , och den har utökats för att lösa icke-linjära problem som involverar begränsningar. Metoden föreslogs först på 1950-talet av Louis Landweber , och den kan nu ses som ett specialfall av många andra mer allmänna metoder.

Grundläggande algoritm

Den ursprungliga Landweber-algoritmen försöker återställa en signal x från (brusiga) mätningar y . Den linjära versionen antar att $y=Ax$ för en linjär operator A . När problemet är i ändliga dimensioner är A bara en matris .

När A är ickesingular är en explicit lösning $x=A^{-1}y$ . Men om A är dåligt konditionerad är den explicita lösningen ett dåligt val eftersom den är känslig för eventuellt brus i data y . Om A är singular existerar inte ens denna explicita lösning. Landweber-algoritmen är ett försök att regularisera problemet och är ett av alternativen till Tikhonov-regularisering . Vi kan se att Landweber-algoritmen löser:

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

med en iterativ metod. Algoritmen ges av uppdateringen

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

där relaxationsfaktorn $\omega$ uppfyller $0<\omega <2/\sigma _{1}^{2}$ . Här $\sigma _{1}$ det största singularvärdet för $A$ . Om vi ​​skriver $f(x)=\|Ax-y\|_{2}^{2}/2$ så kan uppdateringen vara skrivet i termer av gradienten

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

och därför är algoritmen ett specialfall av gradientnedstigning .

För dåligt ställda problem måste den iterativa metoden stoppas vid ett lämpligt iterationsindex, eftersom det halvkonvergerar. Detta innebär att iterationerna närmar sig en regulariserad lösning under de första iterationerna, men blir instabila i ytterligare iterationer. Det reciproka av iterationsindexet $1/k$ fungerar som en regulariseringsparameter. En lämplig parameter hittas när missanpassningen $\|Ax_{k}-y\|_{2}^{2}$ närmar sig brusnivån.

Att använda Landweber-iterationen som en regulariseringsalgoritm har diskuterats i litteraturen.

Icke-linjär förlängning

I allmänhet kommer uppdateringarna som genereras av $x_{k+1}=x_{k}-\tau \nabla f(x_{k})$ att generera en sekvens $f(x_{k})$ som konvergerar till en minimering av f närhelst f är konvex och stegstorleken $\tau$ väljs så att $0<\tau <2/(\|\nabla f\|^{2})$ där $\|\cdot \|$ är spektralnormen .

Eftersom detta är en speciell typ av gradientnedstigning finns det för närvarande inte så stor nytta av att analysera den på egen hand som den olinjära Landweber, men sådan analys utfördes historiskt av många samhällen som inte var medvetna om förenande ramverk.

Det olinjära Landweber-problemet har studerats i många artiklar i många samhällen; se till exempel.

Utvidgning till begränsade problem

Om f är en konvex funktion och C är en konvex mängd , då är problemet

$\min _{x\in C}f(x)$

kan lösas genom den begränsade, olinjära Landweber-iterationen, given av:

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

där ${\mathcal {P}}$ är projektionen på uppsättningen C . Konvergens garanteras när $0<\tau <2/(\|A\|^{2})$ . Detta är återigen ett specialfall av projicerad gradientnedstigning (vilket är ett specialfall av framåt-bakåt-algoritmen) som diskuteras i.

Ansökningar

Eftersom metoden har funnits sedan 1950-talet har den anammats och återupptäckts av många forskarsamhällen, särskilt de som studerar illa ställda problem. Inom röntgendatortomografi kallas det SIRT – simultan iterative reconstruction technique. Det har också använts i datorseende- gemenskapen och signalåterställningsgemenskapen. Det används också i bildbehandling , eftersom många bildproblem, såsom deconvolution , är dåligt ställda. Varianter av denna metod har även använts i glesa approximationsproblem och komprimerade avkänningsinställningar .