Geodesic
An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices
Discrete analysis (2023) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

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 $Ω(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.
Publié le : 
@article{DAS_2023_a19,
     author = {Jaros{\l}aw B{\l}asiok and Patrick Lopatto and Kyle Luh and Jake Marcinek and Shravas Rao},
     title = {An {Improved} {Lower} {Bound} for {Sparse} {Reconstruction} from {Subsampled} {Walsh} {Matrices}},
     journal = {Discrete analysis},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2023_a19/}
}
TY  - JOUR
AU  - Jarosław Błasiok
AU  - Patrick Lopatto
AU  - Kyle Luh
AU  - Jake Marcinek
AU  - Shravas Rao
TI  - An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices
JO  - Discrete analysis
PY  - 2023
UR  - http://geodesic.mathdoc.fr/item/DAS_2023_a19/
LA  - en
ID  - DAS_2023_a19
ER  - 
%0 Journal Article
%A Jarosław Błasiok
%A Patrick Lopatto
%A Kyle Luh
%A Jake Marcinek
%A Shravas Rao
%T An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices
%J Discrete analysis
%D 2023
%U http://geodesic.mathdoc.fr/item/DAS_2023_a19/
%G en
%F DAS_2023_a19
Jarosław Błasiok; Patrick Lopatto; Kyle Luh; Jake Marcinek; Shravas Rao. An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices. Discrete analysis (2023). http://geodesic.mathdoc.fr/item/DAS_2023_a19/