Abstract
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×N Hadamard matrix contains a K-sparse vector in the kernel, unless the number of subsampled rows is ?(KlogKlog(N/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. Based on joint work with Jaros?aw B?asiok, Patrick Lopatto, Kyle Luh, and Jake Marcinek.