QR Decomposition

Previously, we derived the normal equations when b was not in the column space

Where x’ is the best possible solution in the least square sense.

 when matrix A is full column rank and thus invertible, the equation can be solved as

However, explicitly forming AᵀA is numerically undesirable, because it destroys orthogonality, amplifies conditioning errors, and severely reduce numerical accuracy.

QR decomposition avoids forming AᵀA and provides a geometrically transparent and numerically stable solution. So, what we trying to do is re-writing matrix A as a matrix Q with orthonormal vectors (=orthogonal and unit length vectors) as its columns. In other words, the columns of Q form an orthonormal basis for the column space of A.

As an example for orthonormal vectors, consider [1 0  0]ᵀ, [0  1  0]ᵀ, and [0  0  1]ᵀ as a set of orthonormal vectors in ℝ³. But it is not the only possible set. Rotating these vectors while preserving their angles produces infinitely many orthonormal bases.

Orthogonal Transformations

We say that for any matrix A ∈ ℝᵐˣⁿ, there exists a QR decomposition such that:

Where Q ∈ ℝᵐˣⁿ is a matrix with orthonormal columns, and R ∈ ℝⁿˣⁿ is a square, invertible, upper triangular matrix (assuming full column rank).

Let q₁, q₂, ..., qₙ be the orthonormal columns of Q. Each column of Q is a unit vector pointing along a fundamental direction in the column space.

For inner product of the columns of such matrix, we would always have:

So, QᵀQ has zeros on the off-diagonal elements and ones on the diagonal elements, which means:

This means Q preserves the Euclidean inner product structure of the space.

Note that for any vector x ∈ ℝⁿ, its Euclidean length is:

Suppose matrix Q acts on vector x. let’s name it y:

Euclidean length of y could be calculated as:

This means that orthogonal transformation Q do not stretch or shrink vectors, and preserve distances:

In the same way, it could be shown that

But orthogonal transformations preserve not only length, but also angles. Consider the angle θ between vector x and z. it is defined as:

Let x’ and z’ be the transformed vectors by Q:

This means that orthogonal transformations preserve angles between all vectors.

Now, let’s go back to the normal equation and replace A with QR:

Or we could say,

This latter form is particularly favorable because R is upper triangular, so the system can be efficiently solved by back substitution, which is computationally fast and reliable. No matrix inverse is required.

We reach the same line if we follow least square problem perspective. We want to minimize the following:

Substituting A=QR

We previously told that orthogonal transformation Q preserve distances:

So, the problem becomes:

Which is the same equation we previously derived.

For the projection matrix P we have:

So, the projection of b onto the column space of A can be obtained by

Thus, any vector b ∈ ℝᵐ can be uniquely decomposed into two orthogonal components as below:

The first term lies inside the column space of A, and the second term lies orthogonal to the column space (in the left null space).

QR decomposition replaces the ill-conditioned normal equations with a geometrically stable coordinate system aligned with the column space of A. QR works directly with orthonormal bases and preserve the geometry of the problem.

There are several ways to compute Q and R, such as the Gram–Schmidt process and Householder reflections. These methods are not discussed here and can be found in references.

There are more powerful decompositions, such as the singular value decomposition (SVD), which is based on the eigen structure of a matrix. So, to understand SVD, we must first discuss eigenvalues and eigenvectors.