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, a_i is columns of A:

• Initialize
• For i =2 to n:
  • , 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 a₂ on q₁:

q_1 + q_{2}^{'} \\ q_{2}^{'}=a_2 - q_1 " title="Rendered by QuickLaTeX.com" height="64" width="250" style="vertical-align: 26px;">

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 a₃ on q₁ and q₂ :

q_1 + q_2 + q_{3}^{'} \\ q_{3}^{'}=a_3 - q_1 - q_2 " title="Rendered by QuickLaTeX.com" height="64" width="421" style="vertical-align: 26px;">

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 a₁ 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 + ... + q_{l-1} + ||q_{l}^{'}||q_l " title="Rendered by QuickLaTeX.com" height="32" width="566" style="vertical-align: 25px;">

Then, we form a matrix using the orthogonal vectors:

For computing R matrix, we will form an upper triangular square matrix:

& & \cdots & \\ 0& ||q_2'|| & & \cdots & \\ 0& 0 & ||q_3'|| & & \vdots \\ \vdots & \vdots & & \ddots & \\ 0& 0 & \cdots & 0 & ||q_L'|| \end{bmatrix} " title="Rendered by QuickLaTeX.com" height="190" width="633" style="vertical-align: 3px;">

If, we compute Q and R, we will get the matrix.

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.