QR decomposition

Let $A$ be an $m \times n$ matrix with linearly independent columns. ( $r ank (A) = n$ )

A = QR

$Q$ is $m \times n$ matrix with orthonormal columns, output of Gram-Schmidt Process $R$ is given by $Q^{⊤} A \in R^{n \times n}$

Lemma 6.3.11

$R$ is upper triangular and invertible $Q Q^{⊤} A = A$

Proof: $R_{ki} = 0 \forall k \in {2 \dots n}, i < k$ We know $q_{k}^{⊤} q_{i} = 0$ $\forall i < k$ Since the subspace $S_{k - 1} = s p an (q_{1} \dots q_{k - 1}) = s p an (a_{1}, \dots, a_{k - 1})$ we get $q_{k}^{⊤} a_{i} = 0$ for all $i = 1, \dots, k - 1$ . Hence $R_{ki} = 0 \forall k \in {2 \dots n}, i < k$ (note that $R = Q^{⊤} A$ )

Moreover, $Q Q^{⊤}$ is projection matrix onto $C (A)$ The least squares solution $\overset{x}{^}$ to $A x = b$ can be calculated by: $A^{⊤} A \overset{x}{^} = A^{⊤} b$ (see Least Square (Data Fitting)) $R^{⊤} Q^{⊤} QR \overset{x}{^} = R^{⊤} Q^{⊤} b$ $R^{⊤} R \overset{x}{^} = R^{⊤} Q^{⊤} b$ $R \overset{x}{^} = Q^{⊤} b$ ( $R^{⊤}$ is invertible)

R is invertible

$N (A) = {0}$ $⟹ N (R) = {0}$ $⟹ R$ is invertible $⟹ R^{⊤}$ is invertible

Properties

$A^{⊤} A = R^{⊤} R$
$(A^{⊤} A)^{- 1} = R^{- 1} (R^{⊤})^{- 1}$
$A^{†} = R^{- 1} Q^{⊤}$
$P = Q Q^{⊤}$
$Q^{⊤} PQ = I$

Thomas Second Brain

Explorer

QR decomposition

Properties

Graph View