= Solution
A full <QR decomposition> of a real $m$ by $n$ <matrix> with $m\ge n$ writes
$$
A=Q\begin{pmatrix}R\\0\end{pmatrix},
$$
where $Q$ is an orthogonal $m$ by $m$ <matrix> and $R$ is upper triangular $n$ by $n$. In the full-column-rank case $R$ is invertible. Equivalently the reduced factorization is $A=Q_1R$ with $Q_1^TQ_1=I_n$. Householder transformations can construct the full factorization.
Let $Q^Tb=\binom{c_1}{c_2}$ with $c_1\in\mathbb R^n$. Since orthogonal transformations preserve the <Euclidean norm>,
$$
\|Ax-b\|_2^2=\|Rx-c_1\|_2^2+\|c_2\|_2^2.
$$
Therefore the <linear least-squares problem> has the full-rank solution
$$
\boxed{Rx^*=c_1,\qquad \min_x\|Ax-b\|_2=\|c_2\|_2.}
$$
Back substitution solves this triangular system without forming $A^TA$. If the <matrix> is rank deficient, use a rank-revealing pivoted factorization and minimize over its independent columns; the minimizer need not be unique. The original PDF minimizes over $x\in\mathbb R^n$; the converted TeX's minimization over $b$ is a transcription error.
Back to article page
