The Kaczmarz Algorithm or the ART

In applied mathematics it is often the case that the solution to our problem cannot be written in closed form, nor can it be calculated exactly in a finite number of steps. In such cases we are forced to find approximate solutions using iterative algorithms; the Newton-Raphson method for solving f( x) = 0 is an example of an iterative method. There are also situations in which, in theory, the solution can be found exactly, assuming infinitely precise calculations, but to do so would be impractical; solving large systems of linear equations is an example of such a problem. We know that, in theory, Gauss elimination will find the solution in a finite number of steps, if there is a unique solution. But, when there are thousands of equations in thousands of unknowns, as is commonly the case in image processing, Gauss elimination is not practical. The Kaczmarz algorithm [124] was devised to solve just such large systems of linear equations. This algorithm was rediscovered, in the context of medical imaging, by Gordon, Bender, and Herman [104], who called it the algebraic reconstruction technique (ART). The ART algorithm is an example of the method of successive orthogonal projections (SOP) [107]. Both ART and its multiplicative version, MART, have block-iterative and simultaneous counterparts, which we shall discuss in subsequent chapters.

Our discussion of the ART will be fairly detailed. The main reason for this is that the ART is the simplest...