Using Alternative Projection Algorithm to solve linear systems

Question

We can find $x^*$ which converges to the intersection point of convex sets using Alternative projection algorithm.

A linear system $$Ax=b$$ can be considered as a set of hyperplanes $H_i := \{x \in R_n| \lt a_i,x \gt = b\}$. Here $A\in R^{mn}$ and $x\in R^n$. Solving the linear systems mean finding the $x^* \in \cap H_{i=1}^{m} $.

I can see the way we can combine above to find solution to a linear system. I can start with $x_0 \in R^n$ and project it to one by one hyper-plane in cyclic manner.

But I am not clear how I can we implement (I have to do code level implementation) this method to find $x^*$. Also, it is important to know, what is the stopping criteria for this method

Appreciate your insight on this.

Answer 1

This is known as Kaczmarz's method. You would typically stop when $\| Ax -b \| / \| b \|$ satisfies a tolerance.

Answer 2

There are some different simple implementations of the Kaczmarz algorithm here.