Detailed Explanation of QR Decomposition by Givens Rotation
Episode 1: QR Decomposition by Classical Gram-Schmidt (CGS)and modified Gram-Schmidt (MGS)
Episode 2: QR Decomposition by Householder Transformation
Episode 3: QR Decomposition by Givens Rotation
In this episode (episode 3), we will go through the Givens Rotation method to compute QR decomposition. Givens rotations are named after Wallace Givens.
If you are unfamiliar with QR decomposition, these are some key points you need to know before we start.
“Q” in QR decomposition represents an orthogonal matrix, which means:
Remarks: for an orthogonal matrix, the dot product of any 2 column vectors in orthogonal matrix must be equal to 0
“R” in QR decomposition represents right (upper) triangular matrix, which means:
Therefore, QR decomposition is sometimes called QU decomposition.
Some Characteristics of QR Decomposition
- QR Decomposition always exists, but may not be unique
- If the determinant of matrix A is not 0 and all diagonal entries of R > 0, then this QR decomposition is unique.
- There are two types of QR decomposition:
a. Full QR Decomposition
b. Reduced QR Decomposition
For simplicity, we will only include full QR decomposition for square matrix here, whereas matrix A is full rank (i.e. All columns are linearly independent).
QR decomposition is also applicable for m x n (m-by-n) matrixes, where m ≥ n.
In that case, Q will be a m x m (m-by-m) matrix and R will be m x n (m-by-n) matrix.
4 Methods to perform QR decomposition
- (Classical) Gram-Schmidt Process (CGS)
- Modified Gram-Schmidt Process (MGS)
- Household Transformation
- Givens Rotation
In this article, we will cover Givens Rotation.
Set-Up
Like the last two episodes, we will go through the steps of QR decomposition and implementation of QR decomposition by Givens Rotation with Python code.
We create a Python class called Matrix, which will be used in our example. First, we create a 3-by-3 Matrix A for our QR decomposition example.
# main.py
# Create the matrix A
A = Matrix(
n_row=3,
n_col=3,
two_d_array=[[2, -1, -2], [-4, 6, 3], [-4, -2, 8]],
)
QR Decomposition by Givens Rotation
We assume you already know what vector projection is. If you do not, you may refer to medium.
Givens Rotation
In the method of Givens Rotation, similar to Gram-Schmidt and Householder Transformation, we try to decompose each column vector in A to a set of linear combinations of orthogonal vectors in Q.
Therefore, we will try to map each column to a set of orthogonal vectors.
Unlike Householder Transformation, we map the column vector to a set of orthogonal vectors by rotating it, instead of reflecting it. This is called the Givens Rotation method. Before going into our 3x3 matrix example, we will introduce the Matrix Rotation Concept with a 2x2 matrix rotation example, illustrated in both graphic and numeric perspective.
Matrix Rotation
In linear algebra, we can use Matrix to perform vector rotation. Here is an example of a 2-by-2 matrix rotation matrix.
By the definition of Trigonometry, in a circle with radius r (x_1), the coordinate of point P is defined as (r cosθ, r sinθ).
If we re-write the radius on the x-axis (x_1) and point P (x_2) in a vector form,
And the Rotation Matrix G is defined as,
This rotation matrix G is rotating the vector x_1 to x_2.
Similarly in quadrant II, by the definition of Trigonometry, in a circle with radius r (x_1), the coordinate of point P is defined as (-r sinθ, r cosθ).
If we re-write the radius on x-axis (x_1) and point P (x_2) in a vector form,
This rotation matrix G is rotating the vector x_1 to x_2.
You can also use a similar concept for quadrant III and quadrant IV, you will get the same result.
This is the rotation matrix G !!!
Example of Matrix Rotation
Example 1:
Example 2:
Example 3:
I hope you would understand more about matrix rotation by the above example.
Noted that the above matrix rotation is performed on a 2-D plane.
Matrix Rotation Example with Our 3-by-3 Matrix
For a matrix with a higher dimension, we cannot rotate the vector on all dimensions. Therefore, we can only rotate two dimensions each time and fix all other dimensions.
For the rotation matrix G, the dimension of G is equal to the dimension of A (i.e. 3-by-3 matrix). We can construct the matrix G similar to the above example, which can be done by expanding the matrix G with a 2-dimension.
If you want to rotate the vector along the x-axis and z-axis, then we select the first and third columns and rows. Then put the (cosθ, -sinθ, sinθ, cosθ) into the 4 intersection positions respectively.
If you want to rotate the vector along the x-axis and y-axis,
If you want to rotate the vector along the y-axis and z-axis,
This is how we can perform rotation on the matrix with higher dimensions.
QR Decomposition by Givens Rotation
Now, let’s get into our example and see how we can use Givens Rotation to perform QR decomposition.
In the first step, we define the G_1 Matrix to rotate the submatrix with columns 1 & 2 and rows 1 & 2. Then, multiply the G_1 matrix with the original matrix A_1. We store the result as A_2 for the next iteration.
In the second step, we define the G_2 Matrix to rotate the submatrix with columns 1 & 3 and rows 1 & 3. Then, multiply the G_2 matrix with the matrix A_2 (result from the first step). We store the result as A_3 for the next iteration.
In the third step, we define the G_3 Matrix to rotate the submatrix with columns 2 & 3 and rows 2 & 3. Then, multiply the G_3 matrix with the matrix A_3 (result from the first step).
After all the iterations to convert matrix A into an upper-triangular matrix (R matrix), we need to find the Q matrix now.
Now we got both the Q matrix and the R matrix.
[Step-by-Step Python Code] QR Decomposition by Householder Transformation:
# QR Decomposition by Givens Rotation
def QR_Givens_Rotation(M: Matrix) -> tuple():
G_s = []
R = M.deep_copy()
for j in range(R.n_col):
for i in range(R.n_row - 1, j, -1):
if i > j:
col_to_remove = list(
filter(lambda s: s != i and s != j, [i for i in range(R.n_row)])
)
sub = R.sub_matrix(col_to_remove, col_to_remove)
col_vector = sub.get_column_vectors(0)
# Calculate the angle to rotate
theta = math.atan2(
-col_vector[1], col_vector[0]
) # y-coordinate first, then x-coordinate
# Construct Givens Rotation Matrix
G_mat = Matrix(n_row=R.n_row, n_col=R.n_col)
G_mat.set_diagonal()
for row in [i, j]:
for col in [i, j]:
if row == col:
G_mat.values[row][col] = math.cos(theta)
else:
G_mat.values[row][col] = (
1 if row > col else -1
) * math.sin(theta)
# Save the Givens Rotation Matrix
G_s.append(G_mat)
# Calculate the R Matrix for the next iteration
R = G_mat.multiply(R)
# Calculate the Q matrix by multiplying all the transpose of the Givens Matrix
Q = Matrix(M.n_row, M.n_col)
Q.set_diagonal(1)
for G in G_s:
G.transpose()
Q = Q.multiply(G)
G.transpose()
return (Q, R)
# main.py
# ----- Example of Givens Rotation -----
def givens_rotation():
A = Matrix(
n_row=3,
n_col=3,
two_d_array=[[2, -1, -2], [-4, 6, 3], [-4, -2, 8]],
)
print("----- Givens Rotations -----")
A.print_values(matrix_name="A")
Q, R = QR_Givens_Rotation(A)
Q.print_values(matrix_name="Q", num_digits=4)
R.print_values(matrix_name="R", num_digits=4)
print("----- Validate Result -----")
new_A = Q.multiply(R)
new_A.print_values(matrix_name="new_A", num_digits=4)Python Output
Done! We successfully implement Givens Rotation for QR decomposition.
The Python code of the above example can be found on GitHub.
If you like this article, give me a like and share it with your friends. You may also leave me a comment/message too.
