2012/06/26 by Joel Andersson, Andersson, Joel, Jan-Olov Strömberg +1
Engineering · Mathematics · #15A60 #15B52 #42A61 #60B20 #60G50 #94A12 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Microwave Imaging and Scattering Analysis #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1206.5986
openalex publication_date 2012/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 m\gtrsim s(ln s)3ln N. 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 m× N-matrices, by considering what we call low entropy. We also present an improved condition on the so-called restricted isometry constants, δs, ensuring sparse recovery via ℓ1-minimization. We show that δ2s<4/√(41) is sufficient and that this can be improved further to almost allow for a sufficient condition of the type δ2s<2/3.