Numerical Analysis HT24, QR factorisation
Flashcards
What is the (full) $QR$ factorisation of a matrix $A \in \mathbb R^{m \times n}$?
where $Q$ is orthogonal and $R$ is upper-triangular.
Suppose we have a matrix $A \in \mathbb R^{m \times n}$. By breaking down the cases $m \le n$ and $m \ge n$, what are all the possible types of QR factorisation, and what are the dimensions of the matrices involved?
“Fat QR”: When $m \le n$, $A = QR$, $Q \in \mathbb R^{m \times m}$ and $R \in \mathbb R^{m \times n}$:
When $m \ge n$,
“Full QR”: $A = QR$, $Q \in \mathbb R^{m \times m}$ and $R \in \mathbb R^{m \times n}$, $Q$ is made to be square (and hence $Q$ is an orthogonal matrix):
“Thin QR”: $A = QR$, $Q \in \mathbb R^{m \times n}$, $R \in \mathbb R^{n \times n}$, $Q$ is made to be the same size as the original matrix (and hence $Q$ has orthogonal columns, but isn’t an orthogonal matrix):
Suppose we have a matrix $A \in \mathbb R^{m \times n}$ where $m > n$ (i.e. it is a tall and skinny matrix). What is the difference between the full QR and the thin QR, and how are they related?
For the full QR, we have a factorisation
\[A = QR = \begin{bmatrix}Q _ 1 & Q _ 2\end{bmatrix} \begin{bmatrix}R \\\\ 0\end{bmatrix}\]where $Q$ is an $m \times m$ matrix, and $R$ is a $m \times n$ matrix (i.e. $Q$ is made to be square, so it’s orthogonal).
In a thin QR, we have
\[A = Q'R'\]where $Q’$ is the same size as $A$, namely $m \times n$, and $R’$ is $n \times n$.
They are related by the fact that
\[A = Q _ 1 R\]is the thin QR factorisation.
The full QR of an $m \times n$ matrix $A$ is sometimes written
\[A = \begin{bmatrix}Q & Q _ \perp\end{bmatrix} \begin{bmatrix}R \\\\ 0\end{bmatrix}\]
Can you explain the notation $Q _ \perp$?
$Q _ \perp$ is an “orthogonal extension” to $Q$, so all of its columns are orthogonal to the columns of $Q$.
Suppose we have a thin QR of an $m \times n$ matrix $A$ (so $m > n$):
\[A = QR\]
why is not accurate to describe $Q$ as an orthogonal matrix?
Because orthogonal matrices are square matrices satisfying the property $Q^\top Q = I$, but $Q$ here is an $m \times n$ matrix with orthonormal columns.
Suppose $Q$ is an $m \times n$ matrix with orthonormal columns. How can you get the identity from $Q$?
but
\[QQ^\top \ne I\]in general.
Suppose that $Q$ is a $m \times m$ matrix (so it is square) with orthonormal columns. Is it true that $QQ^\top = I$?
Yes. (Though this is not true if $Q$ is not square).
Quickly prove that the QR decomposition of an invertible matrix $A \in \mathbb R^{n \times n}$ is unique.
Suppose $A = Q _ 1 R _ 1$ and $A = Q _ 2 R _ 2$. Then
\[Q _ 2^{-1}Q _ 1 = R _ 2 R _ 1^{-1}\]Since $R _ 2^{-1}$ is also upper triangular, $R _ 2^{-1} R _ 1$ is upper triangular. But $Q _ 2^{-1} Q _ 1$ is also orthogonal, so both of these matrices must be upper-triangular and orthogonal. But there is only one upper-triangular and orthogonal matrix, the identity ($\star$), so we are done.
($\star$: This is not immediate and needs proof).
Via Householder
See also [[Notes - Numerical Analysis HT24, Householder reflectors]]U.
How can Householder matrices $H(w)$ be used to find a QR factorisation of a matrix?
We can turn the first column of a matrix into a vector like
\[\begin{pmatrix}\alpha \\ 0 \\\\ \vdots \\ 0\end{pmatrix}\]Continuing by induction and using block matrices like
\[\begin{pmatrix}1 & a _ {12} &\cdots & a _ {1n} \\ 0 & & H(w) & \\ 0\end{pmatrix}\]we can annihilate all the sub-diagonal entries.
Via Gram-Schmidt
How could you compute the QR factoristion of a matrix $A$ using the Gram-Schmidt process?
Apply the Gram-Schmidt process to the columns of $A$. This gives the columns of $Q$. Then $R$ can either be calculated by keeping track of the row operations being performed or using the identity that
\[R = Q^\top A\]