Categories: Algorithms, Mathematics.

Gram-Schmidt method

Given a set of NN linearly independent vectors ∣V1⟩,∣V2⟩,...\ket{V_1}, \ket{V_2}, ... from a Hilbert space, the Gram-Schmidt method is an algorithm that turns them into an orthonormal set ∣n1⟩,∣n2⟩,...\ket{n_1}, \ket{n_2}, ... as follows (in Dirac notation):

  1. Take the first vector ∣V1⟩\ket{V_1} and normalize it to get ∣n1⟩\ket{n_1}:

    ∣n1⟩=∣V1⟩⟨V1∣V1⟩\begin{aligned} \ket{n_1} = \frac{\ket{V_1}}{\sqrt{\inprod{V_1}{V_1}}} \end{aligned}

  2. Begin loop. Take the next input vector ∣Vj⟩\ket{V_j}, and subtract from it its projection onto every already-processed vector:

    ∣gj⟩=∣Vj⟩−∣n1⟩⟨n1∣Vj⟩−∣n2⟩⟨n2∣Vj⟩−...−∣nj−1⟩⟨nj−1∣Vj⟩\begin{aligned} \ket{g_j} = \ket{V_j} - \ket{n_1} \inprod{n_1}{V_j} - \ket{n_2} \inprod{n_2}{V_j} - ... - \ket{n_{j-1}} \inprod{n_{j-1}}{V_j} \end{aligned}

    This leaves only the part of ∣Vj⟩\ket{V_j} that is orthogonal to all previous ∣nk⟩\ket{n_k}. This why the input vectors must be linearly independent; otherwise ∣gj⟩\ket{g_j} could become zero.

    On a computer, the resulting ∣gj⟩\ket{g_j} will not be perfectly orthogonal due to rounding errors. The above description of step #2 is particularly bad. A better approach is:

    ∣gj(1)⟩=∣Vj⟩−∣n1⟩⟨n1∣Vj⟩∣gj(2)⟩=∣gj(1)⟩−∣n2⟩⟨n2∣gj(1)⟩⋮∣gj⟩=∣gj(j−1)⟩=∣gj(j−2)⟩−∣nj−2⟩⟨nj−2∣gj(j−2)⟩\begin{aligned} \ket{g_j^{(1)}} &= \ket{V_j} - \ket{n_1} \inprod{n_1}{V_j} \\ \ket{g_j^{(2)}} &= \ket{g_j^{(1)}} - \ket{n_2} \inprod{n_2}{g_j^{(1)}} \\ \vdots \\ \ket{g_j} = \ket{g_j^{(j-1)}} &= \ket{g_j^{(j-2)}} - \ket{n_{j-2}} \inprod{n_{j-2}}{g_j^{(j-2)}} \end{aligned}

    In other words, instead of projecting ∣Vj⟩\ket{V_j} directly onto all ∣nk⟩\ket{n_k}, we instead project only the part of ∣Vj⟩\ket{V_j} that has already been made orthogonal to all previous ∣nm⟩\ket{n_m} with m<km < k. This is known as the modified Gram-Schmidt method.

  3. Normalize the resulting orthogonal vector ∣gj⟩\ket{g_j} to make it orthonormal:

    ∣nj⟩=∣gj⟩⟨gj∣gj⟩\begin{aligned} \ket{n_j} = \frac{\ket{g_j}}{\sqrt{\inprod{g_j}{g_j}}} \end{aligned}

  4. Loop back to step 2, taking the next vector ∣Vj+1⟩\ket{V_{j+1}}, until all NN have been processed.

References

  1. R. Shankar, Principles of quantum mechanics, 2nd edition, Springer.