Compute QR decomposition
Gram-Schmidt Orthogonalization
The Gram-Schmidt process is often used to orthogonalize the columns of the matrix A. It produces an orthogonal matrix Q.
Given a matrix A,
,
where, ai is columns of A:
- Initialize
- For i =2 to n:
- , here is the projection of onto
- , here is the projection of onto
- This process produces an orthogonal matrix
Triangularization
Once Q is obtained, the upper triangular matrix R is obtained by multiplying with the original matrix A.
The orthogonal matrix Q is used to triangularize the original matrix A, resulting in an upper triangular matrix R.
Result:
A = QR,
Here,
- A is the original matrix
- Q is orthogonal matrix
- R is upper triangular
Orthogonal Matrix Property:
here,
- is the transpose of Q,
- I is identity matrix.
Step by step Implementations
Using Gram-Schmidt Process:
First, perform normalization.
Here, denotes the norm of
Then, we project a2 on q1:
q_1 + q_{2}^{'} \\ q_{2}^{'}=a_2 -
Here,
- " title="Rendered by QuickLaTeX.com" height="20" width="108" style="vertical-align: 28px;"> is the inner product between and
- is the residual of the projection, orthogonal to
After this project, we normalize the residuals:
Then, we project a3 on q1 and q2 :
q_1 +
Here,
- is residual which is orthogonal to and
We repeatedly perform alternating steps of normalization, where projection residuals are divided by their norms, and projection steps, where a1 is projected according to , until a set of orthonormal vectors is obtained as .
Residuals are expressed in terms of normalized vectors as:
for l =1, …, L , we define
Therefore, we can write the projections as:
.q_1 + ... +
Then, we form a matrix using the orthogonal vectors:
For computing R matrix, we will form an upper triangular square matrix:
&
If, we compute Q and R, we will get the matrix.
QR Decomposition in Machine learning
QR decomposition is a way of expressing a matrix as the product of two matrices: Q (an orthogonal matrix) and R (an upper triangular matrix). In this article, I will explain decomposition in Linear Algebra, particularly QR decomposition among many decompositions.