I am the author of the package for tomographic reconstruction <https://github.com/kulvait/KCT_cbct> I have implemented CGLS/CGNR , algorithm which applies conjugate gradients on normal equation


$$
A^\top A x = A^\top b
$$
I use CGLS/CGNR as a default algorithm for many tomographic problems. Let's say $x\_i$ is the solution after $i$-th iteration. I compute sequence of solutions. I report the norm of discrepancy
$$
d\_i = \|Ax\_i-b\|
$$
and the norm of residual
$$
r\_i = \|A^\top A x\_i -A^\top b\|
$$
to see the speed of convergence based on sequences $(r\_i)$ and (d\_i).


I note that the norm of residual $(r\_i)$ is not always decreasing monotonously but sometimes it jumps up. As conjugate gradients guarantee to minimize norm of error, this is expected behavior. What is interesting I have never seen for any problem the sequence of norm of discrepancy $(d\_i)$, which is non monotonous. Now the question is is that just coincidence?


So I would like to prove or to show an counterexample for the following **claim**.


For all positive definite $A^\top A$ the CGLS behaves such that
$$
\|Ax\_{i+1}-b\| \leq \|Ax\_{i}-b\|
$$



Does norm of discrepancy decrease monotonously in CGLS/CGNR
Let $(x\_i)$ be sequence of solutions to CGLS/CGNR and let $x^\*$ be a solution of
$$A^\top A x^\* = A^\top b$$


AS CG minimizes $A$ norm of error over growing Krylov subspace, CGLS/CGNR minimizes $A^\top A$ norm of error which is


$$\|x^\* - x\_i\|\_{A^\top A} = \|A x^\* - A x\_i\|$$
thus we have
$$\|A x^\* - A x\_{i+1}\| \leq \|A x^\* - A x\_i\|$$


Now from the properties of the least squares solution we can decompose
$$b = A x^\* + b^\perp, \mbox{where} $$
$b^\perp$ is orthogonal to the column space of $A$ and thus
$$\|b - A x\_{i}\| = \|b^\perp\| + \|A x^\* - A x\_{i}\|.$$
Therefore we conclude that the statement
$$\|A x\_{i+1} - b\| \leq \| A x\_{i} - b \|$$
is true.


Thanks to Zdeněk Strakoš for outlining this answer.


