Why an economy size $QR$ decmoposition (reduced $QR$ decmoposition) of $A^T$ suffices to find the solution of $Ax = b$ with minimal norm?

Question

Let $m < n, A \in \mathbb R^{m×n}$. Assume that $A$ has rank $m$. Let $b \in \mathbb R^m$. Why an economy size $QR$ decmoposition (reduced $QR$ decmoposition) of $A^T$ suffices to find the solution of $Ax = b$ with minimal norm?

Answer 1

Suppose that $A^T = QR$ is an economy $QR$ factorization: $Q$ has orthonormal columns and $R$ is nonsingular and upper triangular. Then we are free to extend to a full $QR$ factorization $A^T = \begin{pmatrix} Q & Q' \end{pmatrix} \begin{pmatrix} R \\ 0 \end{pmatrix}$. If $x$ solves $Ax = b$, then we must have $x^TA^T = b^T$ so

$$ x^T\begin{pmatrix} Q & Q' \end{pmatrix} \begin{pmatrix} R \\ 0 \end{pmatrix} = b^T. $$

If we define $y^T := x^T\begin{pmatrix} Q & Q' \end{pmatrix}$, then $y^T\begin{pmatrix} R \\ 0 \end{pmatrix} = b^T$ where $y$ and $x$ have the same magnitude, since \begin{pmatrix} Q & Q' \end{pmatrix} is orthogonal. If we write $y^T = \begin{pmatrix} y_1^T & y_2^T \end{pmatrix}$, then we must have $y_1^TR = b^T$, or equivalently $R^Ty_1 = b$, which is a lower triangular system we can easily solve. Since we want a minimum norm solution, we must set $y_2 = 0$. Thus, multiplying by $\begin{pmatrix} Q & Q' \end{pmatrix}^T$ on both sides of $y^T = x^T\begin{pmatrix} Q & Q' \end{pmatrix}$, we observe

$$ x^T = \begin{pmatrix} \underbrace{y_1^T}_{=b^TR^{-1}} & \underbrace{y_2^T}_{=0} \end{pmatrix} \begin{pmatrix} Q^T \\ Q'^T \end{pmatrix} = b^TR^{-1}Q^T, $$

so $x = QR^{-T}b$. Note that $Q'$ never enters into our final expression for $x$ so we are fine using the economy $QR$ and never must compute the full $QR$.

Also note that $R^{-T}b$ can be computed in $O(n^2)$ operations using forward substitution and $Q(R^{-T}b)$ is just an $O(n^2)$ matrix-vector multiplication, so once the economy $QR$ is computed, this complexity for finding the minimum norm solution is $O(n^2)$.