QR Factorization

• Reduced QR Factorization
• columns of 𝑄 are an orthonormal basis for range(𝐴)
• Full QR Factorization
• Gram-Schmidt method for QR factorization

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Reduced QR Factorization
Consider an mxn matrix A = 𝒂𝟏 𝒂𝟐 … 𝒂𝒏−𝟏 𝒂𝒏

successive spaces spanned by the columns of A:

𝒂𝟏 ⊆ 𝒂𝟏, 𝒂𝟐 ⊆ 𝒂𝟏, 𝒂𝟐, 𝒂𝟑 ⊆…

The idea of QR factorization is the construction of a sequence of orthonormal vectors 𝒒𝟏, 𝒒𝟐 , … that
span these successive spaces.

Assume that A 𝜖 𝙍𝑚x𝑛 (m > n) has full rank n (All n columns are independent)

We want the sequence 𝒒𝟏 , 𝒒𝟐 , … to have the property

𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝒋 = 𝒒𝟏 , 𝒒𝟐 , … 𝒒𝒋 j=1,…,n
Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata
 𝒂𝟏 𝒂2 𝒂𝑛 𝒒𝟏 𝒒2 𝒒𝑛 ----(*)

mxn mxn nxn

• As A 𝛜 𝙍𝑚x𝑛 (m > n) is assumed to be of full rank n, the diagonal entries 𝒓𝒌𝒌 are nonzero.

• If (*) holds, then 𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝑘 can be expressed as linear combinations of 𝒒𝟏 , 𝒒𝟐 , … 𝒒𝑘 .

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata
 𝒂𝟏 = 𝑟11 𝒒𝟏
𝒂2 = 𝑟12 𝒒𝟏 +𝑟22 𝒒2
𝒂2 = 𝑟13 𝒒𝟏 +𝑟23 𝒒2 + 𝑟33 𝒒3
⋮
𝒂𝑛 = 𝑟1𝑛 𝒒𝟏+𝑟2𝑛 𝒒2 + ⋯ + 𝑟𝑛𝑛 𝒒𝑛

As a matrix formula, we have ෡𝑹

A=𝑸 ෡

෡ is m x n with orthonormal columns (𝑸′

where 𝑸 ෡ 𝑸෡ = 𝑰). If A is square, then 𝑸
෡ is orthogonal.

෡ is n x n non-singular, upper triangular matrix (𝑟𝑘𝑘 > 0).

and 𝑹

Such a factorization is called a Reduced QR factorization of A.

• The invertibility of the upper-left k x k block of the triangular matrix implies that, conversely,
𝒒𝟏 , 𝒒𝟐 , … 𝒒𝑘 can be expressed as linear combinations of 𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝑘 .

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Range of a matrix A 𝛜 𝙍𝑚x𝑛 , R(A) = {A𝑥|𝑥 ∈ 𝑅 𝑛 }

suppose 𝐴 has linearly independent columns with QR factors 𝑄, 𝑅.

𝑄 has the same range as 𝐴:

𝑦 ∈ range(𝐴)
⇐⇒ 𝑦 = 𝐴𝑥 for some 𝑥
⇐⇒ 𝑦 = 𝑄𝑅𝑥 for some 𝑥
⇐⇒ 𝑦 = 𝑄𝑧 for some 𝑧
⇐⇒ 𝑦 ∈ range(𝑄)

columns of 𝑄 are an orthonormal basis for range(𝐴)

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Ex:
A=

෡𝑹
=𝑸 ෡

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Full QR Factorization

For full QR factorization of A 𝛜 𝙍𝑚𝑥𝑛 (m ≥ n) , an additional (m – n) orthonormal columns are

appended to 𝑸෡ so that it becomes an m x m unitary matrix Q.

A = 𝑄෠ ෨ 𝑅෠ = QR
𝑄
0

In the process, rows of zeros are appended to R so that it becomes an m x n matrix R, still upper-triangular.

In the full QR factorization, Q is m x m, R is m x n, and the last (m-n) columns of Q are multiplied by
zeros in R.

In the reduced QR factorization, the silent columns and rows are removed. Now Q is m x n, R is n x n,
and none of the rows of R are necessarily zero.

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

 mxn mxn nxn mxn mxn mx(m-n) mxn

Note that in the full QR factorization, the columns 𝑞𝑗 for j > n are orthogonal to range(A).

Assuming A is of full rank n, they constitute an orthonormal basis for range𝐴⊥ (the space orthogonal to
range(A)), i.e, for null (𝐴′).

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

 Applications

The QR factorization to solve

• the pseudo-inverse of a matrix with linearly independent columns

• the inverse of a nonsingular matrix

• projection on the range of a matrix with linearly independent columns

• linear equations

• least squares problems

• constrained least squares problems

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

 Pseudo-inverse of matrix with independent columns

Suppose A 𝛜 𝙍𝑚𝑥𝑛 has linearly independent columns.

This implies that 𝐴 is tall or square (𝑚 ≥ 𝑛)

The pseudo-inverse of 𝐴 is defined as 𝐴† = (𝐴′ 𝐴)−1 𝐴′

This matrix exists, because the Gram matrix (𝐴′ 𝐴) is non-singular.

𝐴† is a left inverse of 𝐴: 𝐴† A = (𝐴′ 𝐴)−1 (𝐴′ 𝐴) = 𝐼.

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Pseudo-inverse of matrix in terms of QR Factors

𝐴† = (𝐴′ 𝐴) −1 𝐴′

𝐴† = ((𝑄𝑅)′ (QR))−1 (QR)′

= (𝑅′ Q′ QR)−1R′ 𝑄′

= (𝑅′ R)−1 R′ 𝑄′

= R−1 (𝑅′) −1 R′𝑄′

= R−1 𝑄′

For square nonsingular 𝐴 this is the inverse: A−1 = R−1 𝑄′

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Solution of Ax = b by QR Factorization
To solve A𝑥= 𝑏 for 𝑥, where A 𝛜 𝙍𝑚𝑥𝑛 .

If A = QR is a QR factorization, then we can write QR𝑥 = 𝑏

⇒ R𝑥 = 𝑄 ′𝑏

The right-hand side of this equation is easy to compute, if Q is known,

The system of linear equations implicit in the left-hand side is also easy to solve because it is
triangular.

This suggests the following method for computing the solution to Ax = b:

1. Compute a QR factorization A = QR.

2. Compute 𝑦 = Q'𝑏.
3. Solve R𝑥 = 𝑦 for 𝑥.
However, it is not the standard method for such problems. Gaussian elimination is the algorithm generally used in practice,
since it requires only half as many numerical operations.
Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata
 The LS Problem

The QR matrix decomposition allows us to compute the solution to the Least Squares problem.

OLS gives us the closed from solution in the form of the normal equations.

But when we want to find the actual numerical solution they aren’t really useful.

In Least Squares problem we want to solve the following equation: X𝛽 = 𝑦

Usually 𝛽መ = 𝑋 −1 𝑦 does not exist as we might have more observations than variables and 𝑋 −1 might not exist.

Instead, we try to find some 𝛽መ that minimizes the objective function σ(𝑦 − 𝑋𝛽)2 .

Taking derivatives with respect to 𝛽መ and setting to zero will lead us to the normal equations and
provides a closed-form solution.

Alternative way: QR Factorization!

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata
Solving the LS problem Using the QR factorization
X𝛽 = 𝑦

Assuming the columns of X to be Linearly independent, X=QR

⇒ (QR) 𝛽 = 𝑦

⇒ 𝛽መ = R−1 𝑄′ 𝑦 [Existence of Pseudo Inverse of X]

This means that all we need to do is find an inverse of R, transpose Q, and take the product. That will
produce the OLS coefficients.

We don’t even need to compute the Variance-Covariance matrix and its inverse (𝑋 ′ 𝑋)−1 which is
how OLS solutions are usually presented.

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

 Projection on range
Range of a matrix A 𝛜 𝙍𝑚x𝑛 , R(A) = {A𝑥|𝑥 ∈ 𝑅 𝑛 }

suppose 𝐴 has linearly independent columns with QR factors 𝑄, 𝑅.

𝑄 has the same range as 𝐴 [Shown previously]

⇒ Columns of 𝑄 are an orthonormal basis for range(𝐴)

We know that if B = {𝑣1 , 𝑣2 , … , 𝑣𝑝 } is an orthogonal basis

for 𝑊 in 𝑅 𝑛 .

Define a matrix P =[𝑣1 𝑣2 … . 𝑣𝑝 ] then, 𝑃𝑟𝑜𝑗𝑊 (𝑦) =

P𝑃𝑇 𝑦
Hence (𝑄𝑄′)𝑥 is the projection of 𝑥 on the range of 𝑄

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

QR using Gram-Schmidt Orthogonalisation

Let A be an m x n matrix with n independent columns.

To find the QR factors of A.

Apply Gram Schmidt orthogonalisation to obtain Q from the columns of A.

⇒ Columns of Q will span the Column Space of A.

Once we have Q we can solve for R easily from QR = A ⇒ R = 𝑄′ 𝐴

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Householder Decomposition

The use of Householder matrices, also termed a Householder reflections, is the most commonly
used method for performing the QR decomposition.

If u is an m × 1 vector, the Householder matrix defined by

A Householder matrix is orthogonal and symmetric.

By a proper choice of u, 𝐻𝑢A zeros out all the elements below a diagonal element 𝑎𝑖𝑖 , and so it is
an ideal tool for the QR decomposition.

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

 A Householder matrix is a reflection matrix whose matrix-vector product geometrically describes a
reflection.

Let x be a vector that we wish to reflect in a mirror (hyperplane) that is perpendicular to the vector u.

To find: A formula for the reflected vector. u

𝑥 ′𝑢
The orthogonal projection of x onto the span of u is given by: 𝑢′ 𝑢
𝑢.

𝑥 ′𝑢 𝑥 ′𝑢
∴x- 𝑢 must lie on the mirror. x–2 𝑢
𝑢′ 𝑢 𝑢′ 𝑢

𝑥 ′𝑢
Hence the reflected vector = x – 2 𝑢′𝑢
𝑢

We can write the reflected vector as a matrix-vector multiply with the Householder
matrix:
𝑥′𝑢 𝑢𝑢′
x–2 𝑢′𝑢
𝑢 = (I – 2 𝑢′𝑢
)x

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

Householder’s Idea

Householder's idea is to apply a sequence of Householder reflections (orthogonal matrices) to the

left of A to gradually convert A into an upper-triangular matrix.

The successive matrices have the following structure (blank spaces indicate zeros):

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

 First Step of Householder’s Reflection

To generate a Householder reflection so that

If the first column of the fully-dense matrix above is a, then we want to find a vector v such
that 𝑄𝑣 𝑎=∥a−−∥2e1Qv_a_=‖a_‖2e1, where e1=(1,0,…,0)Te1=(1,0,…,0)T (remember that
reflections preserve lengths of vectors). A short derivation reveals that we want v–v_ such that:

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata

References:

1. Numerical Linear Algebra; Lloyed N. Trefethen, David Bau

2. https://towardsdatascience.com/qr-matrix-factorization-15bae43a6b2
3. ucla_QR; L. Vandenberghe
4. https://www.sciencedirect.com/topics/engineering/householder-matrix
5. http://pi.math.cornell.edu/~web6140/TopTenAlgorithms/Householder.html

Dr. Durba Bhattacharya; St. Xavier’s College(Autonomous), Kolkata