Kaczmarz method
You don't need to be Editor-In-Chief to add or edit content to WikiDoc. You can begin to add to or edit text on this WikiDoc page by clicking on the edit button at the top of this page. Next enter or edit the information that you would like to appear here. Once you are done editing, scroll down and click the Save page button at the bottom of the page.
Overview
The Kaczmarz method, based on the work of Polish Professor Stefan Kaczmarz, is a method for solving linear systems of equations Ax = b. It is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing.
The method needs, unlike most other linear iterative solvers, not a positive definite but only an invertible matrix A. Therefore it can be used in almost all applications (although most other iterative solvers are for special cases much faster than the Kaczmarz method).
Recently, a randomized version of the Kaczmarz method for overdetermined linear systems that converges at an exponential rate was introduced by Thomas Strohmer and Roman Vershynin. This new solver's rate does not depend on the number of equations in the system and outperforms all previously known methods on extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations reveal that the algorithm can converge faster than the conjugate gradient algorithm.
The basic (non randomized) algorithm
Given a full rank real or complex m x n matrix A (n ≤ m) and a real or complex vector b the following iteration computes a better approximation of the equations solution x:
where
The initial value of x is not important for convergence, although it's better if an appropriate value is chosen. The formulae above gives a simple iteration routine. A complete iteration requires m simple iterations.
The new randomized algorithm
It can be shown (see A randomized solver for linear systems with exponential convergence Thomas Strohmer and Roman Vershynin [1]) that the above algorithm runs significantly faster if i is chosen at random (with probability proportional to 
for each simple iteration.
References
- S. Kaczmarz. Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, pages 335-357, 1937.
- A randomized solver for linear systems with exponential convergence Thomas Strohmer and Roman Vershynin [2]
- W. Hackbusch Iterative Lösung großer schwachbesetzter Gleichungssysteme Teubner Studienbücher, 1993, pages 202-203de:Kaczmarz-Methode
Acknowledgement and Attribution Regarding Sources of Content
Some of the initial content on this page may be incorporated in part from copyleft sources in the public domain including wikis such as Wikipedia and AskDrWiki. Drug information for patients came from the The National Library of Medicine. Infectious disease information may have come from the Centers for Disease Control (CDC). Differential Diagnoses are drawn from clinicians as well as an amalgamation of 3 sources: 1.The Disease Database; 2. Kahan, Scott, Smith, Ellen G. In A Page: Signs and Symptoms. Malden, Massachusetts: Blackwell Publishing, 2004:3; 3. Sailer, Christian, Wasner, Susanne. Differential Diagnosis Pocket. Hermosa Beach, CA: Borm Bruckmeir Publishing LLC, 2002:7 .
