Sparse Reconstruction from Hadamard Matrices: A Lower Bound.

We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that for a $N \times N$ Hadamard matrix, one cannot recover all $k$-sparse vectors unless the number of subsampled rows is $\Omega(k \log^2 N)$.