An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices

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 a matrix formed by uniformly subsampling rows of an $N\times N$ Walsh matrix contains a $K$-sparse vector in the kernel, unless the number of subsampled rows is $\mathrm{\Omega }(K\log K\log (N\mathrm{/}K))$ – our lower bound applies whenever $\min(K, N/K)

\log^C N$. Containing a sparse vector in the kernel precludes not only the restricted isometry property, but more generally the application of those matrices for uniform sparse recovery.