*Supported by Siebel Foundation. †Partially supported by the NSF Graduate Research Fellowship Program under grant DGE-1144152. ‡Partially supported by NSF Postdoctoral Fellowship DMS-1702533. §Supported by the Simons Collaboration on Algorithms and Geometry
Matrices -- Discrete Mathematics, Compressed Sensing
We give a short argument that yields a new lower bound on the number of uniformly and independently 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 and independently subsampling rows of an N ×N Walsh 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) > logC 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.
© 2023 Jarosław Błasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek and Shravas Rao cb Licensed under a Creative Commons Attribution License (CC-BY)
Błasiok, J., Lopatto, P., Luh, K., Marcinek, J., & Rao, S. (2019). An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices. arXiv preprint arXiv:1903.12135.