QR factorization

01Understand the idea#

QR factorization rewrites a matrix using perpendicular unit patterns in $Q$ and a triangular mixing rule in $R$. It helps solve least-squares problems by separating “find the target’s pattern coordinates” from “recover the original feature weights.”

You already know dot products, orthonormal columns, and back substitution. QR connects them: use dot products with $Q$ to find desired pattern coordinates, then solve the upper-triangular system involving $R$. The supplied factors save you from constructing an orthonormal basis in this lesson.

A reduced QR factorization writes A=QR. For a matrix with independent columns, Q has orthonormal columns and R is square, upper triangular, with nonzero diagonal entries. The factors are supplied here; use them to fit a target b.

Let Q have columns (1,0,0) and (0,1,0), with target b=(5,3,2). Dot each column with b. The orthonormal-pattern coordinates are 5 and 3.

Q’s columns span the attainable outputs. Their dot products with b are the coordinates of its projection. Since Ax=Q(Rx), the input must satisfy this triangular system:

02In Rx=Q^Tb, the right side is known but x is still unknown#

In $Rx=Q^Tb$, the right side is known but $x$ is still unknown. For rows of $R$ equal to $(2,1)$ and $(0,3)$ and right side $(5,3)$, the bottom row gives $3x_2=3$. Set $x_2=1$, substitute it into $2x_1+x_2=5$, and solve $x_1=2$. Pattern coordinates $(5,3)$ and feature weights $(2,1)$ differ.

Suppose Qᵀb=(5,3) and R has rows (2,1), (0,3). Solve from the bottom: 3x₂=3 gives x₂=1. Then 2x₁+1=5 gives x₁=2.

03For A with m rows and n independent columns, Qᵀ takes b to n pattern coordinates#

For A with m rows and n independent columns, Qᵀ takes b to n pattern coordinates. R mixes the input weights into those coordinates. Back substitution recovers the weights.

Link to this figure ↗Download SVGDownload PNGCopy linkCopy embed

Q can be rectangular, so no square inverse of Q is needed. Its transpose extracts coordinates. A least-squares input still may leave a nonzero residual: the chosen output is the closest one the matrix can produce.

04A closer look#

In a regression fit with independent feature columns, QR lets software find coefficients without explicitly forming an inverse of $A^TA$. A residual can remain because the target may have a component outside the columns’ span. A solvable triangular system does not imply an exact fit to every measurement.