Meaning of sign(aij) for a matrix entry in QR factorization?

Solution 1:

The idea behind the Householder QR decomposition of the matrix $A$ is this: find a reflexion $H$ such that $Ha_1=\lambda e_1$, where $a_1$ is the first column of $A$, and $e_1$ the first basis vector ($1$ in the first index, $0$ everywhere else).

Therefore, $HA$ transforms $A$ in a matrix with zeros in the first column, except the first element of the column.

Then, do the same on the submatrix $A(2:n,2:n)$, with a matrix $H_2$ that is smaller, but it's immaterial, you may consider the block matrix $\bar H_2=\begin{pmatrix} 1 & 0 \\ 0 & H_2\end{pmatrix}$, then the product $\bar H_2 HA$ will have zeros under the diagonal in the first two columns. Then continue likewise with the other columns. The special form of $H$ makes the product much easier to compute than a full matrix product.

Now, the special form of $H$. You can check that $H=I-2\dfrac{vv^T}{||v||^2}$ is a reflexion w.r.t the hyperplane orthogonal to $v$. To choose $v$, consider an isoceles triangle made either of $a_1$ and $||a_1||e_1$, or $a_1$ and $-||a_1||e_1$. And take $v$ to form twice an altitude of this isoceles triangle (that is, it's a diagonal of the parallelogram formed on $a_1$ and $\pm||a_1||e_1$, better with a drawing).

That is,

$$v=a_1\pm||a_1||e_1$$

So we have a choice. Which is better? Imagine $a_1=\lambda e_1$ with $\lambda >0$. Then $a_1-||a_1||e_1=0$ is not a valid vector. It's an extreme case of catastrophic cancellation, but even in more moderate cases, a subtraction tends to yield fewer significant digits, hence a precision loss. To avoid this, it's customary to pick the sign above so that an addition is computed instead. That is,

$$v=a_1+sign(a_{11})||a_1||e_1$$