We investigate the deterministic construction of partial Hadamard matrices for compressed sensing, for linear and sub-linear sparsity regimes. In the linear regime the number of nonzero components $k$ scales proportional to the dimension of the signal $n$, whereas in the sub-linear case it scales like $O(n^alpha)$ for some $alpha in (0,1)$. The construction is based on the polarization theory in the linear, and the deterministic hashing in the sub-liner regime. Simulation results show that the performance of the constructed family is comparable with (even slightly better than) the traditional Gaussian measurement matrices. Moreover, the inherent structure of the resulting matrices allows more robust and low-complexity implementation with a significant gain in computational complexity.