Notes - 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).
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.
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\]What is the flop cost of one iteration of the basic QR algorithm (including the dominant term)?
The main cost comes from calculating the QR factorisation of the matrix at each step.
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 the only upper-triangular matrices are the identity ($\star$), so we are done.
($\star$: This is not immediate and needs proof).