Householder Transformation

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


The Transformation Matrix

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$


Properties

Householder matrices are symmetric and orthogonal: they are reflection matrices


Derivation

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$
  • c246e03bace34da19bf1a18b832f2f23.png 668dcaac3b5f4581abb7a7beca03430d.png
  • 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



QR Decomposition

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$

f97c9d02e5a34d52b0763a544aa742bc.png


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

Hessenberg Decomposition

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


Sources