Efficient transforms and efficient row generation for Kronecker products of Hadamard matrices

摘要

If a Hadamard matrix H_N of order N=BF is a Kronecker product H_FH_B of an order F Hadamard matrix and an order B Hadamard matrix, then transformation by H_N may be implemented by a fast Hadamard transform at coarse scale followed by fast Hadamard transforms at fine scale. Alternatively, transformation by H_N may 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 H_N may 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 H_N may be generated by concatenating selectively modified copies of a corresponding row of H_B. Thus, modulation patterns may be generated on the fly.