QR decomposition ($A=QR$)

A reduced QR decomposition of an $m\times k$ matrix over the real numbers with full column rank, $m\ge k$, writes $A=QR$, where $Q$ is $m\times k$ with orthonormal columns and $R$ is a $k\times k$ upper triangular matrix with positive diagonal. Applying the Gram-Schmidt process to the columns $v_j$ of $A$ constructs $Q=(q_1\cdots q_k)$ and records the coefficientsThis last column identity is exactly the matrix multiplication $A=QR$. The upper triangular matrix records that the $j$th input uses only the first $j$ new directions, while its positive diagonal records the norms of the nonzero orthogonal projection residuals. Since $Q^{T}Q=I$, one also has $R=Q^{T}A$; $Q^T$ denotes the transpose and $I$ the identity matrix. Over the complex numbers, use the conjugate transpose $Q^{\ast }$ in these identities.

For the three-dimensional Gram-Schmidt process example, the exact matrices areFor example, the last column reconstructs asThe diagonal entries are approximately $1.414214,1.224745,1.154701$. Each is a norm of the new direction before it was scaled to length one.

For a linear least-squares problem, the orthogonal projection of $b$ onto the column space of $A$ is $Q{Q}^{T}b$. Hence the minimizing coefficients solve the linear system $Rx=Q^{T}b$ by back substitution. Let $A_2=(v_1{v}_2)$ consist of the first two columns of the example; its reduced factors are $Q_2=(q_1{q}_2)$ and the leading $2\times 2$ block $R_2$ of $R$. For $b=(0,0,1{)}^T$, the linear system $R_{2}x=Q_2^{T}b$ isThus $A_{2}x=(1/3,-1/3,2/3{)}^T$, agreeing with the orthogonal projection computed above, and the minimum Euclidean norm of $A_{2}x-b$ is $1/\sqrt{3}$. The QR decomposition separates building an orthonormal basis from recovering coefficients in the original basis.^[ref]

Let $A=QR$ with $Q^{T}Q=I$ and square invertible upper triangular $R$. The normal equations for linear least squares reduce from $R^{T}Rx=R^T{Q}^{T}b$ to the system in the title. It is solved by back substitution. The geometric identity $\Vert Ax-b{\Vert }_2^2=\Vert Rx-Q^{T}b{\Vert }_2^2+\Vert (I-Q{Q}^T)b{\Vert }_2^2$ proves existence and uniqueness of the minimizer. For tall $Q$, $Q{Q}^T$ is an orthogonal projection, not the identity on the entire observation space.

Let $K$ be block diagonal with $2\times 2$ blocks $J=\left(\begin{array}{cc}0& 1\\ -1& 0\end{array}\right)$. If a real invertible matrix $A$ commutes with $K$, its QR decomposition $A=BC$, with $B$ orthogonal and $C$ upper triangular with positive diagonal, has both $BK=KB$ and $CK=KC$. Indeed $CK{C}^{-1}=B^{-1}KB$, so $E=K^{-1}CK{C}^{-1}$ is orthogonal and upper triangular in $2\times 2$ blocks. Orthogonality forces its off-diagonal blocks to vanish. Its diagonal blocks are $J^{-1}{C}_{i}J{C}_i^{-1}$. For $C_i=\left(\begin{array}{cc}a& b\\ 0& d\end{array}\right)$ with $a,d>0$, this block is $\left(\begin{array}{cc}d/a& -b/a\\ -b/a& (a^2+b^2)/(ad)\end{array}\right)$. Orthogonality of its columns forces $b=0,d=a$, and hence each block is the identity. Thus $E=I$, proving the claim.

If a real $m$-by-$n$ matrix $A$ has full column rank, with $m\ge n$, then $A^{T}A$ is positive-definite. Its upper-triangular Cholesky decomposition $A^{T}A=R^{T}R$, with positive diagonal, is unique. Defining $Q=A{R}^{-1}$ gives $Q^{T}Q=I$ and $A=QR$. Any other such factorization yields another Cholesky factor of $A^{T}A$, so its $R$ and then its $Q$ must agree. This proves existence and uniqueness; it does not assert that forming $A^{T}A$ is the most numerically stable algorithm.

For a full-column-rank $n\times k$ matrix $V$, extend the thin QR decomposition $V=Q_1{R}_1$ to an orthogonal matrix $Q=(Q_1{Q}_2)$. Thenso $Q^T$ maps the column space of $V$ onto the first $k$ coordinate directions. Successive Householder transformations construct the same reduction without first forming a full orthogonal basis.

A linear least-squares problem minimizes $\Vert Ax-b{\Vert }_2$ over $x$. If $A=QR$ has full column rank, orthogonality reduces it to the upper-triangular system formed from the leading block of $R$ and the leading entries of $Q^{T}b$.