ML Wiki

Latest revision as of 22:29, 6 August 2017

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$
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$

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