Adaptive sensing using deterministic partial Hadamard matrices

This paper investigates the construction of deterministic matrices preserving the entropy of random vectors with a given probability distribution. In particular, it is shown that for random vectors having i.i.d. discrete components, this is achieved by selecting a subset of rows of a Hadamard matrix such that (i) the selection is deterministic (ii) the fraction of selected rows is vanishing. In contrast, it is shown that for random vectors with i.i.d. continuous components, no partial Hadamard matrix of reduced dimension allows to preserve the entropy. These results are in agreement with the results of Wu-Verdu on almost lossless analog compression. This paper is however motivated by the complexity attribute of Hadamard matrices, which allows the use of efficient and stable reconstruction algorithms. The proof technique is based on a polar code martingale argument and on a new entropy power inequality for integer-valued random variables.