Kaczmarz metod

Kaczmarz -metoden eller Kaczmarz algoritm är en iterativ algoritm för att lösa linjära ekvationssystem $Ax=b$ . Den upptäcktes först av den polske matematikern Stefan Kaczmarz och återupptäcktes inom bildrekonstruktionsområdet från projektioner av Richard Gordon , Robert Bender och Gabor Herman 1970, där den kallas Algebraic Reconstruction Technique (ART). ART inkluderar positivitetsbegränsningen, vilket gör den olinjär.

Kaczmarz-metoden är tillämplig på alla linjära ekvationssystem, men dess beräkningsmässiga fördel i förhållande till andra metoder beror på att systemet är sparsamt . Det har visat sig vara överlägset, i vissa biomedicinska avbildningstillämpningar, jämfört med andra metoder såsom den filtrerade bakprojektionsmetoden .

Den har många applikationer, allt från datortomografi (CT) till signalbehandling . Det kan också erhållas genom att på hyperplanen, som beskrivs av det linjära systemet, tillämpa metoden för successiva projektioner på konvexa uppsättningar (POCS).

Algoritm 1: Kaczmarz-algoritm

Låt $Ax=b$ vara ett system av linjära ekvationer , låt $m$ vara antalet rader i A , $a_{i}$ vara i $\displaystyle i}:$ e raden av komplex -värderad matris $A$ , och låt $x^{0}$ vara godtycklig komplexvärderad initial approximation till lösningen av $Ax=b$ . För $k=0,1,\ldots$ beräkna:

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

 

 

 

 

()

där $i=k{\bmod {m}},i=1,2,\ldots m$ och ${\overline { a_{i}}}$ betecknar komplex konjugering av $a_{i}$ .

Om systemet är konsistent konvergerar $x^{k}$ till miniminormlösningen , förutsatt att iterationerna börjar med nollvektorn.

En mer allmän algoritm kan definieras med en relaxationsparameter $\lambda ^{k$ }

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

Det finns versioner av metoden som konvergerar till en regulariserad vägd minsta kvadratlösning när den appliceras på ett system av inkonsekventa ekvationer och, åtminstone vad gäller det initiala beteendet, till en lägre kostnad än andra iterativa metoder, såsom den konjugerade gradientmetoden .

Algoritm 2: Randomiserad Kaczmarz-algoritm

2009 introducerades en randomiserad version av Kaczmarz-metoden för $\|a_{i}\|^{2}.$ av Thomas Strohmer och Roman Vershynin där den i -e ekvationen väljs slumpmässigt med sannolikhet proportionell mot

Denna metod kan ses som ett särskilt fall av stokastisk gradientnedstigning .

Under sådana omständigheter konvergerar $x_{k}$ exponentiellt snabbt till lösningen av $Ax=b,$ och konvergenshastigheten beror endast på det skalade villkorstalet ${ \displaystyle \kappa (A)}$ .

Sats. Låt $x$ vara lösningen av $Ax=b.$ Sedan konvergerar algoritm 2 till $x$ i förväntan, med medelfelet:

$\mathbb {E} \|x_{k}-x\|^{2}\leq \left(1-\kappa (A)^{-2}\right)^{k}\cdot \| x_{0}-x\|^{2}.$

Bevis

Vi har

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

 

 

 

 

()

Använder sig av

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

vi kan skriva ( 2 ) som

$\forall z\in \mathbb {C} ^{n}:\quad \sum _{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}}$

 

 

 

 

()

Huvudpoängen med beviset är att se den vänstra sidan i ( 3 ) som en förväntan på någon slumpvariabel. Kom nämligen ihåg att lösningsutrymmet för $j-th$ ekvationen för $Ax=b$ är hyperplanet

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

vars normala är ${\tfrac {a_{j}}{\|a_{j}\|^{2}}}.$ Definiera en slumpmässig vektor Z vars värden är normalerna till alla ekvationer av ${\ displaystyle Ax=b}$ , med sannolikheter som i vår algoritm:

$Z={\frac {a_{j}}{\|a_{j}\|}}$ med sannolikhet ${\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\qquad \qquad \qquad j=1,\ldots ,m$

Sedan ( 3 ) säger det

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

 

 

 

 

()

Den ortogonala projektionen $P$ på lösningsrummet för en slumpmässig ekvation av $Ax=b$ ges av $Pz=z-\langle zx,Z\rangle Z.$

Nu är vi redo att analysera vår algoritm. Vi vill visa att felet ${\|x_{k}-x\|^{2}}$ minskar vid varje steg i genomsnitt (betingat på de föregående stegen) med minst faktorn $(1-\kappa (A)^{-2}).$ Nästa approximation $x_{k}$ beräknas från $x_{k-1}$ som $x_{k}=P_{k}x_{k-1},$ där $P_{1},P_{2} ,\ldots$ är oberoende realiseringar av den slumpmässiga projektionen $P.$ Vektorn $x_{k-1}-x_{k}$ finns i kärnan av $P_{k}.$ Den är ortogonal mot lösningsrummet för ekvationen som ${\displaystyle P_{k}} projicerar på$ , som innehåller vektorn $x_{k}-x$ (kom ihåg att $x$ är lösningen på alla ekvationer). Ortogonaliteten för dessa två vektorer ger då

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

För att slutföra beviset måste vi binda $\|x_{k-1}-x_{k}\|^{2}$ underifrån. Enligt definitionen av $x_{k}$ har vi

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

där $Z_{1},Z_{2},\ldots$ är oberoende realiseringar av den slumpmässiga vektorn $Z.$

Således

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

Nu tar vi förväntan på båda sidor beroende på valet av de slumpmässiga vektorerna ${\displaystyle Z_{1},\ldots ,Z_{k-1}} ($ därav fixar vi valet av de slumpmässiga projektionerna $P_{1},\ldots ,P_{k-1}$ och därmed de slumpmässiga vektorerna $x_{1 },\ldots ,x_{k-1}$ och vi medelvärde över den slumpmässiga vektorn ${\displaystyle Z_{k}} )$ . Sedan

$\mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}=\left(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}}.$

Genom ( 4 ) och oberoende,

$\mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}\leq (1-\kappa (A) )^{-2}){\|x_{k-1}-x\|^{2}}.$

Med de fulla förväntningarna från båda sidor drar vi slutsatsen att

$\mathbb {E} \|x_{k}-x\|^{2}\leq (1-\kappa (A)^{-2})\mathbb {E} {\|x_{k -1}-x\|^{2}}.\blackquare$

Överlägsenheten av detta urval illustrerades med rekonstruktionen av en bandbegränsad funktion från dess olikformigt fördelade samplingsvärden. Det har dock påpekats att den rapporterade framgången av Strohmer och Vershynin beror på de specifika val som gjordes där för att översätta det underliggande problemet, vars geometriska natur är att hitta en gemensam punkt för en uppsättning hyperplan, till ett system av algebraiska ekvationer. Det kommer alltid att finnas legitima algebraiska representationer av det underliggande problemet för vilket urvalsmetoden kommer att fungera på ett sämre sätt.

Kaczmarz-iterationen ( 1 ) har en rent geometrisk tolkning: algoritmen projicerar successivt den aktuella iterationen på hyperplanet som definieras av nästa ekvation. Därför är varje skalning av ekvationerna irrelevant; det kan också ses från ( 1 ) att eventuell (icke-noll) skalning av ekvationerna tar bort. I RK kan man alltså använda $\|a_{i}\|$ eller andra vikter som kan vara relevanta. Specifikt, i det ovan nämnda rekonstruktionsexemplet, valdes ekvationerna med sannolikhet proportionell mot det genomsnittliga avståndet för varje provpunkt från dess två närmaste grannar - ett koncept introducerat av Feichtinger och Gröchenig . För ytterligare framsteg i detta ämne, se och referenserna där.

Algoritm 3: Gower-Richtarik-algoritm

Under 2015 utvecklade Robert M. Gower och Peter Richtarik en mångsidig randomiserad iterativ metod för att lösa ett konsekvent system av linjära ekvationer $Ax=b$ som inkluderar den randomiserade Kaczmarz-algoritmen som ett specialfall. Andra specialfall inkluderar randomiserad koordinatnedstigning, randomiserad Gaussisk härkomst och randomiserad Newtonmetod. Blockversioner och versioner med viktighetssampling av alla dessa metoder uppstår också som specialfall. Metoden har visat sig åtnjuta exponentiell hastighetsminskning (i förväntan) - även känd som linjär konvergens, under mycket milda förhållanden när slumpmässighet kommer in i algoritmen. Gower-Richtarik-metoden är den första algoritmen som avslöjar en "syskon"-relation mellan dessa metoder, av vilka några var oberoende föreslagna tidigare, medan många var nya.

Insikter om Randomized Kaczmarz

Intressanta nya insikter om den randomiserade Kaczmarz-metoden som kan erhållas från analysen av metoden inkluderar:

• Den allmänna hastigheten för Gower-Richtarik-algoritmen återställer exakt hastigheten för den randomiserade Kaczmarz-metoden i det speciella fallet när den reducerades till den.
• Valet av sannolikheter för vilka den randomiserade Kaczmarz-algoritmen ursprungligen formulerades och analyserades (sannolikheter proportionella mot kvadraterna på radnormerna) är inte optimalt. Optimala sannolikheter är lösningen av ett visst semidefinite program. Den teoretiska komplexiteten för randomiserade Kaczmarz med de optimala sannolikheterna kan vara godtyckligt bättre än komplexiteten för standardsannolikheterna. Men hur mycket det är bättre beror på matrisen $A$ . Det finns problem för vilka standardsannolikheterna är optimala.
• När den tillämpas på ett system med matris $A$ som är positiv definitiv, är Randomized Kaczmarz-metoden likvärdig med Stokastisk Gradient Descent (SGD)-metoden (med en mycket speciell stegstorlek) för att minimera den starkt konvexa kvadratiska funktionen $f(x)={\tfrac {1}{2}}x^{T}Ax-b^{T}x.$ Observera att eftersom $f$ är konvex, är minimeringarna av ${ \displaystyle f}$ måste uppfylla $\nabla f(x)=0$ , vilket motsvarar $Ax=b.$ Den "särskilda stegstorleken" är den stegstorlek som leder till en punkt som i den endimensionella linjen som spänns av den stokastiska gradienten minimerar det euklidiska avståndet från den okända(!) minimizern för f {\ $f }$ , nämligen från $x^{*}=A^{-1}b.$ Denna insikt erhålls från en dubbel syn på den iterativa processen (beskrivs nedan som "Optimeringssynspunkt: Begränsning och ungefärlig").

Sex likvärdiga formuleringar

Gower-Richtarik-metoden har sex till synes olika men likvärdiga formuleringar, som ger ytterligare ljus över hur man tolkar den (och, som en konsekvens, hur man tolkar dess många varianter, inklusive randomiserad Kaczmarz):

• 1. Skissa synvinkel: Sketch & Project
• 2. Optimeringssynpunkt: Begränsa och Ungefärlig
• 3. Geometrisk synpunkt: Slumpmässig skärningspunkt
• 4. Algebraisk synpunkt 1: Random Linear Solve
• 5. Algebraisk synpunkt 2: Slumpmässig uppdatering
• 6. Analytisk synvinkel: Slumpmässig fast punkt

Vi beskriver nu några av dessa synpunkter. Metoden beror på 2 parametrar:

• en positiv bestämd matris $B$ som ger upphov till en viktad euklidisk inre produkt $\langle x,y\rangle _{B}:=x^{T }By$ och den inducerade normen

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

• och en slumpmässig matris $S$ med lika många rader som $A$ (och eventuellt slumpmässigt antal kolumner).

1. Skiss och projekt

Givet tidigare iteration $x^{k},$ beräknas den nya punkten ${\displaystyle x^{k+1}} genom att rita en slumpmässig matris$$S$ (i en iid mode från någon fast distribution), och inställning

$x^{k+1}={\underset {x}{\operatörsnamn {arg\ min} }}\|xx^{k}\|_{B}{\text{ med förbehåll för }}S^ {T}Ax=S^{T}b.$

Det vill säga, $x^{k+1}$ erhålls som projektionen av $x^{k}$ på det slumpmässigt skissade systemet ${\ displaystil S^{T}Ax=S^{T}b}$ . Tanken bakom denna metod är att välja $S$ på ett sådant sätt att en projektion på det skissade systemet är väsentligt enklare än lösningen av det ursprungliga systemet $Ax=b$ . Randomiserad Kaczmarz-metod erhålls genom att välja $B$ för att vara identitetsmatrisen, och $S$ för att vara den $i^{th}$ enhetskoordinatvektorn med sannolikhet ${\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2}.} Olika val av B {\$ displaystyle $}$ och $S$ leder till olika varianter av metoden.

2. Begränsa och approximera

En till synes annorlunda men helt likvärdig formulering av metoden (erhållen via lagrangisk dualitet) är

$x^{k+1}={\underset {x }{\operatörsnamn {arg\ min} }}\left\|xx^{*}\right\|_{B}{\text{ med förbehåll för }}x=x^{k}+B^{-1} A^{T}Sy,$

där $y$ också tillåts variera, och där $x^{*}$ är valfri lösning av systemet $Ax=b.$ Följaktligen erhålls ${\displaystyle x^{k+1}} genom att först begränsa uppdateringen till det linjära delutrymmet som sträcks av kolumnerna i den slumpmässiga matrisen$$B^{-1}A^{T}S$ , dvs till

$\left\{h:h=B^{-1}A^{T}Sy,\quad y{\text{ kan variera }}\right\},$

och välj sedan punkten $x$ från detta delutrymme som bäst approximerar $x^{*}$ . Denna formulering kan se förvånande ut eftersom det verkar omöjligt att utföra approximationssteget på grund av det faktum att $x^{*}$ inte är känd (det är trots allt vad vi försöker beräkna!). Det är dock fortfarande möjligt att göra detta, helt enkelt för att $x^{k+1}$ beräknat på detta sätt är detsamma som $x^{k+1}$ beräknat via skissen och projektformuleringen och eftersom $x^{*}$ inte visas där.

5. Slumpmässig uppdatering

Uppdateringen kan också skrivas uttryckligen som

$x^{k+1}=x^{ k}-B^{-1}A^{T}S\vänster(S^{T}AB^{-1}A^{T}S\höger)^{\dolk}S^{T}\vänster (Ax^{k}-b\right),$

där vi med $M^{\dagger }$ betecknar Moore-Penrose-pseudo-inversen av matrisen $M$ . Därför kan metoden skrivas i formen $x^{k+1}=x^{k}+h^{k}$ , där $h^{k}$ är en slumpmässig uppdateringsvektor .

Om man låter $M=S^{T}AB^{-1}A^{T}S,$ kan det visas att systemet $My=S^{T}(Ax^{k}-b)$ har alltid en lösning $y^{k}$ , och att vektorn för alla sådana lösningar ${\displaystyle x^{k+1}-B^{-1}A^{T}Sy^{k}} är$ samma. Därför spelar det ingen roll vilken av dessa lösningar som väljs, och metoden kan också skrivas som $x^{k+1}=x^ {k}-B^{-1}A^{T}Sy^{k}$ . Pseudo-inversen leder bara till en speciell lösning. Rollen för pseudo-inversen är tvåfaldig:

• Det gör att metoden kan skrivas i den explicita "slumpmässiga uppdateringen"-formen enligt ovan,
• Det gör analysen enkel genom den sista, sjätte formuleringen.

6. Slumpmässig fast punkt

Om vi ​​subtraherar $x^{*}$ från båda sidor av den slumpmässiga uppdateringsformeln, beteckna

$Z:=A^{T}S\left(S^{T}AB^{-1}A^ {T}S\right)^{\dolk}S^{T}A,$

och använd det faktum att $Ax^{*}=b,$ kommer vi fram till den sista formuleringen:

$x^{k+1}-x^{*}=\left(IB^{-1} Z\höger)\vänster(x^{k}-x^{*}\höger),$

där $I$ är identitetsmatrisen. Iterationsmatrisen, $IB^{-1}Z,$ är slumpmässig, varav namnet på denna formulering.

Konvergens

Genom att ta villkorade förväntningar i den 6:e formuleringen (villkorad av ${\displaystyle x^{k}})$ får vi

$\mathbb {E} \left.\left[x^{k+1}-x^{*}\right|x^{k}\right]=\left(IB^{-1}\mathbb {E} [Z]\höger)\vänster[x^{k}-x^{*}\höger].$

Genom att ta förväntan igen och använda förväntningarnas tornegenskap får vi

$\mathbb {E} \left[x^{k+1}-x^{*}\right]=(IB^{-1}\mathbb {E} [Z])\mathbb {E} \ vänster[x^{k}-x^{*}\höger].$

Gower och Richtarik visar det

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

där matrisnormen definieras av

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

Dessutom, utan några antaganden om $S$ har man $0\leq \rho \leq 1.$ Genom att ta normer och rulla upp återfallet får vi

Teorem [Gower & Richtarik 2015]

$\left\|\mathbb {E} \left[x^{k}-x^{*}\right]\right\|_{B}\leq \rho ^{k}\|x^{ 0}-x^{*}\|_{B}.$

Anmärkning . Ett tillräckligt villkor för att de förväntade residualerna ska konvergera till 0 är $\rho <1.$ Detta kan uppnås om $A$ har en fullständig kolumnrankning och under mycket milda förhållanden på $S.$ Konvergens av metoden kan etableras även utan hela kolumnrankningsantagandet på ett annat sätt.

Det är också möjligt att visa ett starkare resultat:

Teorem [Gower & Richtarik 2015]

De förväntade kvadratiska normerna (snarare än förväntningsnormer) konvergerar i samma takt:

$\mathbb {E} \left\|\left[x^{k}-x^{*}\right]\right\|_{B}^{2}\leq \rho ^{k}\ vänster\|x^{0}-x^{*}\right\|_{B}^{2}.$

Anmärkning . Denna andra typ av konvergens är starkare på grund av följande identitet som gäller för alla slumpmässiga vektorer $x$ och alla fasta vektorer $x^{*}$ :

$\left\|\mathbb {E} \left[xx^{*}\right]\right\|^{2}=\mathbb {E} \left[\left\|xx^{*}\ höger\|^{2}\höger]-\mathbb {E} \left[\|x-\mathbb {E} [x]\|^{2}\höger].$

Konvergens av Randomized Kaczmarz

Vi har sett att den randomiserade Kaczmarz-metoden uppträder som ett specialfall av Gower-Richtarik-metoden för $B=I$ och $S$ är $i^{th}$ enhetskoordinatvektor med sannolikhet $p_{i}=\|a_{i}\|_{2}^{2}/\|A \|_{F}^{2},$ där $a_{i}$ är den $i^{th}$ raden i $A.$ Det kan kontrolleras genom direkt beräkning att

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

Algoritm 4: PLSS-Kaczmarz

Eftersom konvergensen av den (randomiserade) Kaczmarz-metoden beror på en konvergenshastighet kan metoden göra långsamma framsteg i vissa praktiska problem. För att säkerställa ändlig terminering av metoden har Johannes Brust och Michael Saunders (akademiker) utvecklat en process som generaliserar den (randomiserade) Kaczmarz-iterationen och avslutar i högst $m$ -iterationer till en lösning för det konsistenta systemet $Ax=b$ . Processen är baserad på Dimensionality-reduktion , eller projektioner på lägre dimensionella utrymmen, vilket är hur den härleder sitt namn PLSS (Projected Linear Systems Solver). En iteration av PLSS-Kaczmarz kan betraktas som generaliseringen

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

där $A_{1:k,:}$ är urvalet av rader 1 till $k$ och alla kolumner i $A$ . En randomiserad version av metoden använder $k$ icke upprepade radindex vid varje iteration: $\{i_{1},\ldots ,i_{ k-1},i_{k}\}$ där varje $i_{j}$ är i $1,2,...,m$ . Iterationen konvergerar till en lösning när $k=m$ . I synnerhet eftersom $A_{1:m,:}=A$ gäller att

$Ax^{m+1}=Ax^{m}+AA^{T} (AA^{T})^{\dolk }(b-Ax^{m})=b$

och därför är $x^{m+1}$ en lösning på det linjära systemet. Beräkningen av iterater i PLSS-Kaczmarz kan förenklas och organiseras effektivt. Den resulterande algoritmen kräver bara matris-vektorprodukter och har en direkt form

    
    

    
        
        
        
                
        
        
        
        
          algoritm  PLSS-Kaczmarz  är  inmatning:  matris  A  höger sida  b  utgång:  lösning  x  så att  Ax=b  x := 0  ,  P = [0]  för  k  i  1,2,...,m  gör  a  :=  A( i  k  ,:)' // Välj ett index i  k  i 1,...,m utan omsampling  d  :=  P' * a  c  1  :=  norm(a)  c  2  :=  norm(d)  c  3  :=  (b  i  k  -x'*a)/((c1  -  c2  )  *(c1  +  c2  )  )  p  := c  3  *(a - P*(P'*a))  P  := [ P, p/norm(p) ] // Lägg till en normaliserad uppdatering  x  := x + p  returnerar  x 

Anteckningar

• 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 , vol. 35, s. 355–357
• Chong, Edwin KP; Zak, Stanislaw H. (2008), An Introduction to Optimization (3:e upplagan), John Wiley & Sons, s. 226–230
•   Gordon, Richard ; Bender, Robert; Herman, Gabor (1970), "Algebraisk rekonstruktionsteknik (ART) för tredimensionell elektronmikroskopi och röntgenfotografering", 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), Stoppa bröstcancer nu! Att föreställa sig avbildningsvägar mot att söka, förstöra, bota och vaksam väntan på bröstcancer före metastasering. I: Breast Cancer - A Lobar Disease, redaktör: Tibor Tot , Springer, s. 167–203
•   Herman, Gabor (2009), Fundamentals of computerized tomography: Image reconstruction from projection (2nd ed.), Springer, ISBN 9781846287237
• Censor, Yair ; Zenios, SA (1997), Parallell optimering: teori, algoritmer och tillämpningar , New York: Oxford University Press
• Aster, Richard; Borchers, Brian; Thurber, Clifford (2004), Parameter Estimation and Inverse Problems , Elsevier
•   Strohmer, Thomas; Vershynin, Roman (2009), "En randomiserad Kaczmarz-algoritm för linjära system med exponentiell konvergens" (PDF) , Journal of Fourier Analysis and Applications , 15 ( 2): 262–278, arXiv : math/0702226 , doi : 41s100000. -008-9030-4 , S2CID 1903919
•   Needell, Deanna; Srebro, Nati; Ward, Rachel (2015), "Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm", Mathematical Programming , 155 (1–2): 549–573, arXiv : 1310.5715 , doi : 10.10107-s40107-s. 7 , S2CID 2370209
•    Censor, Yair; Herman, Gabor ; Jiang, M. (2009), "A not on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin", 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), "Comments on the randomized Kaczmarz method", Journal of Fourier Analysis and Applications , 15 (4): 437–440, doi : 10.1007/s00041-009-9082-0 , S2CID 14806322
• Bass, Richard F. ; Gröchenig, Karlheinz (2013 ) , "Relevant sampling of band-limited functions", Illinois Journal of Mathematics , 57 (1): 43–58, arXiv : 1203.0146 , doi : 10.1215/ijm/1403534485 7485 S7485 34485 ,  
•   Gordon, Dan (2017), "A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates", Numerical Algorithms , 77 (4): 1141–1157, doi : 10.1007/s11075-017-0356-3 , S2CID 1794974
• Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Proceedings of the 2011 2nd International Congress on Computer Applications and Computational Science, vol. 2, Springer, s. 465–469
•   Gower, Robert; Richtarik, Peter (2015a), "Randomiserade iterativa metoder för linjära system", SIAM Journal on Matrix Analysis and Applications , 36 ( 4): 1660–1690, arXiv : 1506.03296 , doi : 10.1137 /15M102ID 924C 924C 924C
• Gower, Robert; Richtarik, Peter (2015b), "Stokastisk dubbel uppstigning för att lösa linjära system", 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

externa länkar

• [1] En randomiserad Kaczmarz-algoritm med exponentiell konvergens
• [2] Kommentarer om den randomiserade Kaczmarz-metoden