Efficient transforms and efficient row generation for kronecker products of hadamard matrices

Abstract

If a Hadamard matrix Hof order N=BF is a Kronecker product HHof an order F Hadamard matrix and an order B Hadamard matrix, then transformation by Hmay be implemented by a fast Hadamard transform at coarse scale followed by fast Hadamard transforms at fine scale. Alternatively, transformation by Hmay be achieved by performing order B transforms on columns of a two-dimensional array and order B transforms on rows of the array. As another alternative, transformation by Hmay be achieved by computing intermediate values based on linear combinations of input elements and then computing linear combinations of the intermediate values. For compressive signal acquisition, any row of Hmay be generated by concatenating selectively modified copies of a corresponding row of H. Thus, modulation patterns may be generated on the fly.