**R – Aaron Schlegel**, and kindly contributed to R-bloggers)

The more common approach to QR decomposition is employing Householder reflections rather than utilizing Gram-Schmidt. In practice, the Gram-Schmidt procedure is not recommended as it can lead to cancellation that causes inaccuracy of the computation of , which may result in a non-orthogonal matrix. Householder reflections are another method of orthogonal transformation that transforms a vector into a unit vector parallel with . The Householder reflection matrix with normal vector takes the form:

Thus we need to build so that for some constant and .

Since is orthogonal, and . Therefore, . The sign is selected so it has the opposite sign of (we’ll use for the remaining definitions). The vector we seek is thus:

With the unit vector defined as . The corresponding Householder reflection is then:

###### QR Decomposition with Householder Reflections

The Householder reflection method of QR decomposition works by finding appropriate matrices and multiplying them from the left by the original matrix to construct the upper triangular matrix . As we saw earlier, unlike the Gram-Schmidt procedure, the Householder reflection approach does not explicitly form the matrix. However, the matrix can be found by taking the dot product of each successively formed Householder matrix.

Consider the matrix .

We find the reflection of the first column vector , .

With a corresponding Householder matrix:

With , we then find by :

replaces in the next iteration. Now we move to and . To this end we only consider the submatrix of :

Thus, is equal to:

Therefore, the corresponding Householder matrix is equal to:

The first column and first row are added to the resulting matrix to keep it .

Then we find :

Moving to and , the submatrix of is thus . Therefore, is equal to:

The corresponding Householder matrix is then:

Which is the factorization in the QR decomposition method. The factorization of QR decomposition is found by multiplying all the matrices together as mentioned earlier.

Thus we obtain the same result as we did utilizing the Gram-Schmidt procedure.

###### Householder Reflection QR Decomposition in R

The following function implements the Householder reflections approach to QR decomposition. The `bdiag()`

function in the Matrix package is used in constructing the matrices as seen above in the calculation of .

qr.householder <- function(A) { require(Matrix) R <- as.matrix(A) # Set R to the input matrix A n <- ncol(A) m <- nrow(A) H <- list() # Initialize a list to store the computed H matrices to calculate Q later if (m > n) { c <- n } else { c <- m } for (k in 1:c) { x <- R[k:m,k] # Equivalent to a_1 e <- as.matrix(c(1, rep(0, length(x)-1))) vk <- sign(x[1]) * sqrt(sum(x^2)) * e + x # Compute the H matrix hk <- diag(length(x)) - 2 * as.vector(vk %*% t(vk)) / (t(vk) %*% vk) if (k > 1) { hk <- bdiag(diag(k-1), hk) } # Store the H matrix to find Q at the end of iteration H[[k]] <- hk R <- hk %*% R } Q <- Reduce("%*%", H) # Calculate Q matrix by multiplying all H matrices res <- list('Q'=Q,'R'=R) return(res) }

Use the function to compute the QR decomposition of the following matrix with Householder reflections.

A <- rbind(c(2,-2,18),c(2,1,0),c(1,2,0)) A ## [,1] [,2] [,3] ## [1,] 2 -2 18 ## [2,] 2 1 0 ## [3,] 1 2 0

qr.householder(A) ## $Q ## 3 x 3 Matrix of class "dgeMatrix" ## [,1] [,2] [,3] ## [1,] -0.6666667 0.6666667 -0.3333333 ## [2,] -0.6666667 -0.3333333 0.6666667 ## [3,] -0.3333333 -0.6666667 -0.6666667 ## ## $R ## 3 x 3 Matrix of class "dgeMatrix" ## [,1] [,2] [,3] ## [1,] -3.000000e+00 2.220446e-16 -12 ## [2,] -1.165734e-16 -3.000000e+00 12 ## [3,] 1.554312e-16 0.000000e+00 -6

The only package that I found that directly implements the Householder reflection approach to QR is the pracma package.

library(pracma)

house <- householder(A) house ## $Q ## [,1] [,2] [,3] ## [1,] -0.6666667 0.6666667 0.3333333 ## [2,] -0.6666667 -0.3333333 -0.6666667 ## [3,] -0.3333333 -0.6666667 0.6666667 ## ## $R ## [,1] [,2] [,3] ## [1,] -3.000000e+00 2.220446e-16 -12 ## [2,] -1.165734e-16 -3.000000e+00 12 ## [3,] -1.554312e-16 0.000000e+00 6

###### References

En.wikipedia.org. (2017). QR decomposition. [online] Available at: https://en.wikipedia.org/wiki/QR_decomposition#Using_Householder_reflections [Accessed 10 Apr. 2017].

http://www.math.iit.edu/~fass/477577_Chapter_4.pdf

Trefethen, L. and Bau, D. (1997). Numerical linear algebra. 1st ed. Philadelphia: SIAM.

The post QR Decomposition with Householder Reflections appeared first on Aaron Schlegel.

**leave a comment**for the author, please follow the link and comment on their blog:

**R – Aaron Schlegel**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...