  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.
