Householder matrices for thin QR updating

159 Views Asked by At

Suppose you have a QR decomposition of the form:

$X=QR$

(Where $X$ is an arbitrary matrix of size $(n \times p)$, $Q$ is an orthogonal matrix of size $(n \times n)$ and $R$ is an upper trapezoidal matrix of size $(n \times p)$).

I have read that you can obtain a QR decomposition of $X$ with one of it's rows removed using the original QR decomposition of $X$.

Going by this paper, you can use an $(n \times n)$ permutation matrix, $P$ and an $(n \times n)$ Householder matrix $H$, which are both dependent on which row is to be removed from $X$, in order to calculate:

$(PQH)(HR) = \begin{bmatrix} 1 & \textbf{0} \\ \textbf{0} & \bar{Q} \end{bmatrix}\begin{bmatrix} v \\ \bar{R} \end{bmatrix}$

Where $\bar{Q}$ and $\bar{R}$ are the updated QR decomposition for $X$ with the row of interest removed.

However, I was wondering; does anyone know, can this be done for the thin QR decomposition?

I.e. instead of having; $Q$ as $(n \times n)$ and $R$ as $(n \times p)$ could this be done for $Q$ as $(n \times p)$ and $R$ as $(p \times p)$ using a Householder matrix of dimensions $(p \times p)$?

1

There are 1 best solutions below

0
On

I am denoting the dimensions in the subscript and indexing matrices will be denoted using superscripts. You can partition the Matrix $Q_{n\text{x}n}$ into $[Q^1_{n\text{x}p}, Q^2_{n\text{x}(n-p)}]$ , and the matrix $R_{n\text{x}p}$ into $\begin{bmatrix}R^1_{p\text{x}p} \\ R^2_{(n-p)\text{x}p}\end{bmatrix}$. Due to the fact that $R_{n\text{x}p}$ is upper trapezoidal, we must have $R^2_{(n-p)\text{x}p}=0$. This gives us $A_{n\text{x}p}=Q_{n\text{x}n}R_{n\text{x}p}=Q^1_{n\text{x}p}R^1_{p\text{x}p}$.