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 unitvector $v$ is specified by the following transformation:
 $P = I  2 v v^T$
 So this is just rank1 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 roundoff 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 subdiagonal 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
Sources