On the Theorem of Uniform Recovery of Random Sampling Matrices

DOI10.1109/TIT.2014.2300092MaRDI QIDQ2986492zbMATH OpenOpenAlexFDO

Authors Jan-Olov Strömberg, Joel A. E. Andersson

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.5986

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an $s$-sparse signal from linear measurements (with high probability) is known to be $mgtrsims(lns{)}^{3}lnN$. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of $mimesN$-matrices, by considering what we call emph{low entropy}. We also present an improved condition on the so-called restricted isometry constants, $delt{a}_s$, ensuring sparse recovery via $el{l}^1$-minimization. We show that $delt{a}_{2s}<4/sqrt41$ is sufficient and that this can be improved further to almost allow for a sufficient condition of the type $delt{a}_{2s}<2/3$.

Cited in

(15)

• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
• Stability analysis of a class of sparse optimization problems
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• A null-space-based weightedl₁minimization approach to compressed sensing
• A duality proof of sampling localisation in relaxation spectrum recovery
• Matrix algebra and sampling theory: The case of the Horvitz-Thompson estimator
• scientific article; zbMATH DE number 7370639 (Why is no real title available?)
• A new metric for the recoverability of sparse signals
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• A weighted _1-minimization approach for sparse polynomial chaos expansions
• Worst-case recovery guarantees for least squares approximation using random samples
• On the sparsity of Lasso minimizers in sparse data recovery
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels

This page was built for publication: On the Theorem of Uniform Recovery of Random Sampling Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986492)