Sponsor
*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
Published In
ArXiv preprint
Document Type
Pre-Print
Publication Date
2023
Subjects
Matrices -- Discrete Mathematics, Compressed Sensing
Abstract
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.
Rights
© 2023 Jarosław Błasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek and Shravas Rao cb Licensed under a Creative Commons Attribution License (CC-BY)
DOI
10.19086/a.74802
Persistent Identifier
https://archives.pdx.edu/ds/psu/40452
Citation Details
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.
Description
Pre-Print