Fast Hadamard transform based on a simple matrix factorization

This correspondence presents a simple factorization of the Hadamard matrix which is used to develop a fast algorithm for the Hadamard transform. The matrix decomposition is of the form of the Kronecker products of identity matrices and successively lower order Hadamard matrices. This decomposition leads very clearly to a sparse-matrix factorization of the Hadamard matrix.