An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices

Jarosław Błasiok, Patrick Lopatto, Kyle Luh +2

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 p…