An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices

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\times N$ Walsh matrix contains a $K$-sparse vector in the kernel, unless the number of subsampled rows is $\Omega (K\log K\log (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.

Revised version. Published in Discrete Analysis

Cited by in corpus (1)

• (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless