
Visual Explanation of the Conjugate Gradient Algorithm - mercurymercury
https://pwacker.com/CG.html
======
nimish
I always thought it was simpler to explain by using the only trick linear
algebra has: switch to a basis where your problem is easiest, then switch
back.

Sylvester's law of inertia proves existence + gram-schmidt constructs that
change of basis

~~~
zzleeper
I was recently re-reading how to solve systems via QR and realized that the
key trick was switching basis. But it took me a while to understand that, in
between all the extra stuff. Now you are telling me that most of LA is like
that and wow, so many things make sense now!

Do you have any additional linear algebra tricks?

~~~
nimish
Linear algebra done right is IMO the best book on it.

But a lot of it is simply exploiting linearity to reduce to a working in the
most convenient subspaces. Finding and constructing them is a major task.

------
jl2718
CG, most elegant of quadratic methods. Now let’s talk about why you wouldn’t
use it. 1. In the form given, you need to know the terms of the quadratic. 2.
If you know the terms, you can compute a stable point using QR, which is more
efficient. 3. IIRC CG has better numerical stability than QR, but only under
strict quadratic assumptions. 4. If you don’t have the form of the objective,
but you know it’s quadratic, and you can compute a gradient, then it also
works, but errors in the gradient compound. 5. If it’s not quadratic, then you
have the same issue. You can try to account for this using resets or more
complicated methods, but then, 6. For so many problems, the stability proof
becomes too onerous or the evaluations become less efficient than simply doing
more steps of gradient descent, which is why this is still the dominant method
in neural networks, despite so much effort on ‘our’ part to find more
efficient solvers.

------
vladTheInhaler
Here is another resource I came across when learning about the conjugate
gradient method for a class on finite elements. I wish I had found this back
then!

[https://www.cs.cmu.edu/~quake-papers/painless-conjugate-
grad...](https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf)

~~~
clemParis
Thanks ! Are there other great math papers or articles with a similar "without
the agonizing pain" approach, for other topics that might be interesting ?

