We recently learned about LU factorization in class [1]. However, matrix manipulation and decomposition is not limited to LU factorization. There are other decomposition techniques that come in handy in solving a variety of matrix problems. QR decomposition is one of particular interest [2]. QR decomposition is a very powerful tool to solve the Ax=b problem, and other problems such as solving for eigenvalue and eigenvectors [3-4].

What makes QR decomposition particularly useful is that it decomposes a matrix A (mxn, where m is greater than or equal to n) to Q, an orthogonal matrix, and R, an upper triangular matrix. An orthogonal matrix Q, satisfies Q’Q=I, where Q’ is the transpose of Q [5]. A useful property of Q is that it preserves the length of a vector v, when performing the transformation Qv. If A is invertible, or nonsingular, then this factorization is unique with the constraint that the diagonal elements of R are positive. One method of computing the QR decomposition is to use Gram-Schmidt [6]. However, there are some more efficient methods such as the Householder reflections [7], or Givens rotations [8].

Once the QR decomposition of A is obtained it is rather easy to solve the Ax=b problem.

Ax=b

QRx=b

Use the property that Q is orthogonal and Q’Q=I:

Q’QRx=Q’b

IRx=Q’b

Rx=Q’b

Note that R is upper triangular and using back substitution, one can easily solve for x [9].

I once solved an interesting problem that involved using qr factorization to compute the path of a trajectory where only the data up to time t is available. The problem asked to solve the Ax=b problem where the matrix A and b are known up to time t, and the goal is to get as much information about the vector x by using one step of back substation, i.e. cx=b, x=b/c. Furthermore, one is not able to calculate the inverse of matrix A, or recompute everything up to step t. Rather; the solution should use the previous results and the current data to come up with the new results. The solution involved taking the QR decomposition of a new matrix using a portion of the previous R matrix, padded by the new portion of matrix A. However, the introduction of the class of such problems is more important than the particularities of the detailed solution.

To compute only a portion of the results at time t, and ignore the complete solution is called a forward pass. In the forward pass one would get some idea of what the solution is. However, in order to get the complete solution, one will have to go back and use the newly obtained results to smooth out the previous solutions and solve for the unknowns. This is called a backward pass, and in the case of the problem mentioned above it is simply backward substitution.

Below are my results from the problem discussed. Figure 1 shows sample trajectory data. Figure 2 shows a forward pass of the data. Figure 3 shows the backward pass, and Figure 4 is the combination of all three figures over-plotted. The forward pass has a clear indication of where the trajectory is headed, even though it is not as smooth as the backward pass results.

Figure 1

Figure 2

Figure 3

Figure 4

Why would anyone be interested in only a portion of the solution? Since real-time systems might not have the computational capability to solve a problem completely in a short period of time, sometimes users are content with only an approximation of the results. For instance, imagine if the trajectory problem above was solving for the position of an unidentifiable flying object in space.

PeachyPi

References

[1] http://en.wikipedia.org/wiki/LU_decomposition

[2] http://planetmath.org/encyclopedia/QRFactorization.html

[3] http://en.wikipedia.org/wiki/Eigenvalue

[4] http://en.wikipedia.org/wiki/QR_algorithm

[5] http://en.wikipedia.org/wiki/Orthonormal_matrix

[6] http://en.wikipedia.org/wiki/Gram-schmidt

[7] http://planetmath.org/encyclopedia/HouseholderReflection.html

[8] http://en.wikipedia.org/wiki/Givens_rotation

[9] http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/CURVE-linear-system.html