1
$\begingroup$

First of all, I'd like to make clear that I'm talking about the Gram-Schmidt Conjugation process (in the context of conjugate gradient method for optimization), which instead of making a set of n independent vectors orthonormal, makes a set of n independent vectors conjugates - that is: expressable in the form

enter image description here

(where vector u_i and vector u_j are conjugates, or sometimes, "A-orthogonal").

Understandably, this formula is going to be very similar to Gram-Schmidt Orthogonalization, since the process is the same - but instead of projecting (and subtracting) some vector v onto all the previous orthogonal vectors and subtracting, we're projecting on to the all the previous conjugate vectors and subtracting.

So, the question is what this "projection matrix" is. In the paper/explanation I'm working through to understand Conjugate Gradient, there is two pages dedicated to the explanation of Gram-Schmidt Conjugation Process (pages 31-32 in pdf) and there is a proof of what the "projection" matrix is, but I don't understand it. I recommend you look at it in the paper but here is a screenshot:

enter image description here

I get equation (36), but kind of get lost after that. I get why they're premultiplying, since the whole definition of conjugate is that they abide to that property of u_i(T) * A*u_j = 0, but I really don't get the new subscript "j" which I haven't seen before and the removal of the summation.

If someone could explain it step by step that would be really good,

Thank you!

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The goal is to find $\beta_{ij}$ such that $d_{(i)}^TAd_{(j)}=0$.

We transpose equation $(36)$ and premultiply it to $Ad_{(j)}$

In the very next line, the summation seems to vanish, that is because if $k \ne j$, then $d_{(k)}^TAd_{(j)}=0$. Hence only one term is left.

After which, we can solve for $\beta_{ij}$.

$\endgroup$
5
  • $\begingroup$ Thank you so much! It's quite beautiful how it all goes together. Tried it out on the whiteboard and made so much sense... thanks. $\endgroup$
    – adam dhalla
    Mar 26, 2021 at 8:54
  • $\begingroup$ oh! Also was wondering how you were able to transpose the vectors inside the summation when you transposed both sides of the equation. $\endgroup$
    – adam dhalla
    Mar 26, 2021 at 9:02
  • $\begingroup$ we have $(A+B)^T=A^T+B^T$ isn't it? $\endgroup$
    – Siong Thye Goh
    Mar 26, 2021 at 9:03
  • $\begingroup$ Yes, but I was wondering since there is a multiplication within the summation (the B_ij matrix and the d_k vector) we transpose both of these at the same time $$\left( \beta _{ij}d_{j}\right) ^{T}=d_{j}^{T}\beta _{ij}^{T}$$ - why in the equation did they not switch order? Does the B matrix not have a tranpose since we assume it is symmetric? $\endgroup$
    – adam dhalla
    Mar 26, 2021 at 10:32
  • $\begingroup$ $\beta_{i,j}$ is a scalar $\endgroup$
    – Siong Thye Goh
    Mar 26, 2021 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .