Linear Algebra - Orthogonalization - Building an orthogonal set of generators

About

Original stated goal: Find the projection of b orthogonal to the space V spanned by arbitrary vectors <math>{v_1} , \dots , {v_n}</math>

Articles Related

Computation

• Input: A list <math>{v_1} , \dots , {v_n}</math> of vectors over the reals
• output: A list of mutually orthogonal vectors <math>v_1^* , \dots , v_n^*</math> such that

<MATH>Span \{ v_1^* , \dots , v_n^* \} = Span \{v_1, \dots , v_n\}</MATH>

# output: a list of mutually orthogonal vectors.
def orthogonalize(vlist):
    vstarlist = []
    for v in vlist:
        # project orthogonal find the next orthogonal vector
        # and make iteratively a longer and longer list of mutually orthogonal vectors.
        vstarlist.append(project_orthogonal(v, vstarlist))
    return vstarlist

where:

• the project orthogonal function is the high dimensional projection computation of mutually orthogonal vectors.

Lemma: Throughout the execution of orthogonalize, the vectors in vstarlist are mutually orthogonal.

Proof: by induction, using the fact that each vector added to vstarlist is orthogonal to all the vectors already in the list.

Property

Order matters

If we run the procedure orthogonalize twice, once with a list of vectors and once with the reverse of that list, the output lists will not be the reverses of each other.

Matrix Equation has a matrix composed of mutually orthogonal vector and an upper triangle matrix

• First iteration, since the set <math>\{v_0\}</math> is trivially a set of mutually orthogonal vectors:
  • <math>v^*_0 = v_0</math>
  • or as matrix equation: <math>[v_1] = [v^*_1] [1]</math>
• Second Iteration, <math>v^*_1</math> is the the projection orthogonal of <math>v_1</math> to <math>v^*_0</math> then:
  • <math>v_1 = v^*_1 + \sigma_{01} v^*_0</math>
  • or as matrix equation: <math>[v_1] = \begin{bmatrix}v^*_0 & v^*_1 \end{bmatrix} \begin{bmatrix}\sigma_{01} \\ 1 \end{bmatrix}</math>
• Third iteration: <math>v^*_2</math> is the projection of <math>v_2</math> orthogonal to <math>v^*_0</math> and <math>v^*_1</math> :
  • <math>v_2 = v^*_2 + (\sigma_{02} v^*_0 + \sigma_{12} v^*_1)</math>
  • or as matrix equation: <math>[v_2] = \begin{bmatrix}v^*_0 & v^*_1 & v^*_2 \end{bmatrix} \begin{bmatrix}\sigma_{02} \\ \sigma_{12} \\ 1 \end{bmatrix}</math>
• After N Iterations, we will get this matrix equation (formed of two matrix) expressing original vectors in terms of starred vectors. It's not a matrix multiplication

<MATH> \begin{bmatrix} \begin{array}{r|r|r|r} \, \: \; \> & \\ \, \: \; \> & \\ \\ v_0 & v_1 & v_2 & \dots & v_n \ \\ \ \\ \end{array} \end{bmatrix} = \begin{bmatrix} \begin{array}{r|r|r|r} v^*_0 & v^*_1 & v^*_2 & \dots & v^*_n \end{array} \end{bmatrix} \begin{bmatrix} 1 & \sigma_{01} & \sigma_{02} & \dots & \sigma_{0n} \\ & 1 & \sigma_{12} & \dots & \sigma_{1n} \\ & & 1 & \dots & \sigma_{2n} \\ & & & \ddots & \vdots \\ & & & & 1 \\ \end{bmatrix} </MATH>

The two matrices on the right are special:

• Columns of first one are mutually orthogonal.
• Second is upper triangular.