Linear Algebra - Orthogonalization - Building an orthogonal set of generators

Card Puncher Data Processing

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>

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:

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:





Discover More
Card Puncher Data Processing
Linear Algebra - Basis of a Vector Space

A basis for vector space V is a linearly independent set of generators for V. Thus a set S of vectors of V is a basis for V if S satisfies two properties: Property B1 (Spanning) Span S = V, and Property...
Card Puncher Data Processing
Linear Algebra - Closest point in higher dimension than a plane

Solving closest point in the span of many vectors Goal: An algorithm that, given a vector b and vectors v1, . . . , vn, finds the vector in Span {v1, . . . , vn} that is closest to b. Special case:...
Card Puncher Data Processing
Linear Algebra - Find a basis computation problem

Find a basis for a vector space Example: Find a basis for the null space of By the dot-product definition of matrix-vector multiplication, a vector v is in the null space of A if the dot-product...
Card Puncher Data Processing
Linear Algebra - Generators of a Vector Space

The generators for the set of vectors are the vectors in the following formula: where is a generating set for {[3, 0, 0], [0, 2, 0], [0, 0, 1]} is a generating set for . = Span {[3, 0,...
Card Puncher Data Processing
Linear Algebra - Orthogonal complement Vector Space

Let U be a of W. For each vector b in W, we can write b as the following projections: where: is in U, and is orthogonal to every vector in U. Let V be the set . V is the orthogonal complement...



Share this page:
Follow us:
Task Runner