Householder Transformation (also "Householder Reflection") is an orthogonal reflection transformation:

- it reflex the vectors in the columns of the matrix such that
- the first vector has all zeros except the first element

Reflection transformation:

- Reflection across the plane orthogonal to some unit-vector $v$ is specified by the following transformation:
- $P = I - 2 v v^T$
- So this is just rank-1 update of the identity matrix
- such $P$ is called "Householder transformation" (also: Householder Reflection or Householder Matrix)
- and $v$ is the "Householder vector"
- when we multiply $P x$, $x$ is reflected around $\text{span}(v)^{\bot}$
- if $v$ is not unit vector, we need to normalize it
- let $\beta = 2 / \| v \|^2$, so we can simply write $P = I - \beta v v^T$

Householder matrices are symmetric and orthogonal: they are reflection matrices

So we have $P = I - 2vv^T$:

- this is reflection across the plane orthogonal to $v$
- suppose we have some vector $x$ and want to reflect it such that it becomes parallel to some unit vector $y$
- here we want to reflect around the place that is between $y$ and $x$ - that bisects the angle between them
- the vector orthogonal to this place is $x - \| x \| y$
- so let $u = x - \| x \| y$ and $v = u / \| u \|$
- $\| u \|^2 = (x - \| x \| y)^T (x - \| x \| y) = \ ...$
- $... \ = \|x\|^2 - 2 \| x \| x^T y + \| x \|^2 \| y \|^2 = \ ...$
- $... \ = \|x\|^2 - 2 \| x \| x^T y + \| x \|^2 = \ ...$ (since $y$ is unit vector)
- $... \ = 2 \|x\|^2 - 2 \| x \| x^T y$

- $Px = (I - 2 v v^T) x = x - 2 \cfrac{u u^T x}{\| u \|^2} = \ ...$
- $... \ = x - 2 \cfrac{(x - \| x \| y) (x - \| x \| y)^T x}{2 \|x\|^2 - 2 \| x \| x^T y} = \ ...$
- $... \ = x - 2 \cfrac{(x - \| x \| y) (x^T - \| x \| x^T y)}{2 \|x\|^2 - 2 \| x \| x^T y} = \ ...$
- $... \ = x - (x - \| x \| y) = \| x \| y$

- so when we apply $P$ to some $x$, we get $\| x \| y$

We use such transformations for zeroing elements

- we want to zero all elements of $x$ except the first one, so we need $P x = \pm \alpha e_1$
- we know that if $P x = \pm \alpha e_1$ and $P$ is Householder reflection with $y = e_1$, then $P x =\pm \alpha e_1 = \| x \| e_1$, so $\alpha = \pm \| x \| = \rho \| x \|$ where $\rho = \pm 1$
- let $z = x - \alpha e_1$ and $u = z / \| z \|$
- so [math]z = x - \alpha e_1 = x - \rho \| x \| e_1 = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} - \rho \| x \| \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} = \begin{bmatrix} x_1 - \rho \| x \| \\ x_2 \\ \vdots \\ x_n \end{bmatrix} [/math]
- we can choose any $\rho$, but often it's $\rho = -\text{sign}(x_1)$ - this is better for round-off errors

Like in case of LU Decomposition, where we applied a series of Gauss Transformation changes, we can do the same and perform a series of Householder Transformations

- so if we select $y = \pm e_1$ (where $e_1$ is the matrix with 1 on position 1 and rest are zeros)
- then it will zero all elements of $x$ except the first one
- thus by the appropriate choice of $H$ we can take $A$ and zero all the sub-diagonal elements
- can do that multiple times for each column of $A$

This way we can perform QR Decomposition:

def qr_householder(A): m, n = A.shape Q = np.eye(m) # Orthogonal transform so far R = A.copy() # Transformed matrix so far for j in range(n): # Find H = I - beta*u*u' to put zeros below R[j,j] x = R[j:, j] normx = np.linalg.norm(x) rho = -np.sign(x[0]) u1 = x[0] - rho * normx u = x / u1 u[0] = 1 beta = -rho * u1 / normx R[j:, :] = R[j:, :] - beta * np.outer(u, u).dot(R[j:, :]) Q[:, j:] = Q[:, j:] - beta * Q[:, j:].dot(np.outer(u, u)) return Q, R

Instead of using it for reducting the matrix to Triangular, we can use Householder Transformation to reduce a matrix to Hessenberg Matrix