logo

Matrix QR Decomposition 📂Matrix Algebra

Matrix QR Decomposition

Overview

Efficient matrix decomposition requires several conditions, but before efficiency, whether the decomposition itself is possible or not can be important. QR decomposition is a matrix decomposition method that does not require the condition of being a square matrix.

Definition

For a matrix $A := \begin{bmatrix} \mathbb{a}_{1} & \cdots & \mathbb{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$ with coefficients $n$, let’s define the subspace generated by the column vectors up to the $i$th

$$ S_{i} (A) := \text{sp} \left\{ \mathbb{a}_{1}, \cdots , \mathbb{a}_{i} \right\} $$

When generating a vector space, since $i$ can be larger, it is assumed that

$$ S_{1} (A) \subset S_{2} (A) \subset \cdots S_{n} (A) $$

will hold.

Of course, for a matrix made up of orthonormal vectors

$$ \widehat{Q} : = \begin{bmatrix} \mathbb{q}_{1} & \cdots & \mathbb{q}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n} $$

$S_{1} (\widehat{Q}) \subset S_{2} (\widehat{Q}) \subset \cdots S_{n} (\widehat{Q})$ also holds.

If relationships such as satisfying $S_{i} (A) = S_{i} (\widehat{Q})$ can be found, since $\widehat{Q}$ will be easier to handle, matrix $A$ would also become easier to handle.

$$ \begin{align*} \mathbb{a}_{1} =& r_{11} \mathbb{q}_{1} \\ \mathbb{a}_{2} =& r_{12} \mathbb{q}_{1} + r_{22} \mathbb{q}_{2} \\ &\vdots \\ \mathbb{a}_{n} =& r_{1n} \mathbb{q}_{1} + \cdots + r_{nn} \mathbb{q}_{n} \end{align*} $$

The relationship we want to find will appear in forms like above, and the multiplication of matrices is organized as below.

$$ A = \begin{bmatrix} \mathbb{a}_{1} & \cdots & \mathbb{a}_{n} \end{bmatrix} = \begin{bmatrix} \mathbb{q}_{1} & \cdots & \mathbb{q}_{n} \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} := \widehat{Q} \widehat{R} $$

And finding

$$ \widehat{Q} : = \begin{bmatrix} \mathbb{q}_{1} & \cdots & \mathbb{q}_{n} \end{bmatrix} \\ \widehat{R} := \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} $$ that satisfies such a multiplication of matrices is exactly what QR decomposition is.

Algorithm

Let’s say $\begin{bmatrix} \mathbb{a}_{1} & \cdots & \mathbb{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$.

**Step 1. $j=1$

Calculate $r_{11}$ that satisfies $\mathbb{a}_{1} = r_{11} \mathbb{q}_{1}$ and $| \mathbb{q}_{1} | = 1$.

**Step 2. $j= 2, 3, \cdots , n$

  • Step 2-1. Calculate $r_{ij} = \mathbb{q}_{i}^{\ast}\mathbb{a}_{j}$ for $i = 1,2, \cdots , j-1$.
  • Step 2-2. Calculate the temporary vector as follows: $$ \mathbb{v}_{j} = \mathbb{a}_{j} - \sum_{i = 1}^{j-1} r_{ij} \mathbb{q}_{i} = \mathbb{a}_{j} - \sum_{i=1}^{j-1} (\mathbb{q}_{i}^{\ast}\mathbb{a}_{j} ) \mathbb{q}_{i} $$
  • Step 2-3. Calculate $r_{jj} = | \mathbb{v}_{j} |$.
  • Step 2-4. Calculate the following: $$ \mathbb{q}_{j} = {{ \mathbb{v}_{j} } \over {r_{jj} }} $$
  • Here, since $R$ is given as an upper triangular matrix and is calculated by $r_{jj} = | \mathbb{v}_{j} |$, it is always guaranteed to be $r_{jj} > 0$, and therefore the existence of $R^{-1}$ can be known.
  • On the other hand, as you may have noticed from the notation of $\widehat{Q}$ and $\widehat{R}$, more specifically, the decomposition mentioned above is called a reduced QR decomposition, i.e., rQR decomposition.
  • The full QR decomposition, i.e., fQR decomposition, is achieved in the same way as the singular value decomposition (../340), by composing $Q = \begin{bmatrix} \widehat{Q} & \mathbb{q}_{n+1} & \cdots & \mathbb{q}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m}$ made of orthonormal vectors and filling the bottom with $0$, to form $R = \begin{bmatrix} \widehat{R} \\ O \end{bmatrix} \in \mathbb{C}^{m \times n}$.

Existence

Matrix $A \in \mathbb{C}^{m \times n}$ always has a QR decomposition.

Uniqueness

Invertible matrix $A \in \mathbb{R}^{m \times m}$ has only one rQR decomposition.

Explanation

Although it’s good that the existence and uniqueness are guaranteed, there’s practically no proof to speak of. Especially regarding uniqueness, despite proving it to be unique, the fact that it tolerates inversions of signs among other things makes it a messy fact the more you delve into it, so it’s recommended to just acknowledge it and move on.